Approximate max-flow min-cut theorems are mathematical propositions in network flow theory. Approximate max-flow min-cut theorems deal with the relationship between maximum flow rate ("max-flow") and minimum cut ("min-cut") in a multi-commodity flow problem. The theorems have enabled the development of approximation algorithms for use in graph partition and related problems.
A "commodity" in a network flow problem is a pair of source and sink nodes. In a multi-commodity flow problem, there are commodities, each with its own source
si
ti
Di
Di
si
ti
In a multicommodity flow problem, max-flow is the maximum value of, where is the common fraction of each commodity that is routed, such that
fDi
\varphi
In a uniform multicommodity flow problem, there is a commodity for every pair of nodes and the demand for every commodity is the same. (Without loss of generality, the demand for every commodity is set to one.) The underlying network and capacities are arbitrary.[1]
In a product multicommodity flow problem, there is a nonnegative weight for each node
v\inV
G=(V,E)
u\inV
See also: Linear programming. In general, the dual of a multicommodity flow problem for a graph is the problem of apportioning a fixed amount of weight (where weights can be considered as distances) to the edges of such that to maximize the cumulative distance between the source and sink pairs.[1]
The research on the relationship between the max-flow and min-cut of multicommodity flow problem has obtained great interest since Ford and Fulkerson's result for 1-commodity flow problems. Hu[2] showed that the max-flow and min-cut are always equal for two commodities. Okamura and Seymour[3] illustrated a 4-commodity flow problem with max-flow equals to 3/4 and min-cut equals 1. Shahrokhi and Matula[4] also proved that the max-flow and min-cut are equal provided the dual of the flow problem satisfies a certain cut condition in a uniform multicommodity flow problem. Many other researchers also showed concrete research results in similar problems[5] [6] [7]
For a general network flow problem, the max-flow is within a factor of of the min-cut since each commodity can be optimized separately using
1/k
There are two theorems first introduced by Tom Leighton and Satish Rao in 1988[8] and then extended in 1999.[1] Theorem 2 gives a tighter bound compared to Theorem 1.
Theorem 1. For any, there is an -node uniform multicommodity flow problem with max-flow and min-cut
\varphi
f\leO\left(
| \varphi | |
| logn |
\right)
Theorem 2. For any uniform multicommodity flow problem,
| \Omega\left( | \varphi |
| logn |
\right)\lef\le\varphi
\varphi
To prove Theorem 2, both the max-flow and the min-cut should be discussed. For the max-flow, the techniques from duality theory of linear programming have to be employed. According to the duality theory of linear programming, an optimal distance function results in a total weight that is equal to the max-flow of the uniform multicommodity flow problem. For the min-cut, a 3-stage process has to be followed:[1] [6]
Stage 1: Consider the dual of uniform commodity flow problem and use the optimal solution to define a graph with distance labels on the edges.
Stage 2: Starting from a source or a sink, grow a region in the graph until find a cut of small enough capacity separating the root from its mate.
Stage 3: Remove the region and repeat the process of stage 2 until all nodes get processed.
Theorem 3. For any product multicommodity flow problem with commodities,
| \Omega\left( | \varphi |
| logk |
\right)\lef\le\varphi
\varphi
The proof methodology is similar to that for Theorem 2; the major difference is to take node weights into consideration.
In a directed multicommodity flow problem, each edge has a direction, and the flow is restricted to move in the specified direction. In a directed uniform multicommodity flow problem, the demand is set to 1 for every directed edge.
Theorem 4. For any directed uniform multicommodity flow problem with nodes,
| \Omega\left( | \varphi |
| logn |
\right)\lef\le\varphi
\varphi
The major difference in the proof methodology compared to Theorem 2 is that, now the edge directions need to be considered when defining distance labels in stage 1 and for growing the regions in stage 2, more details can be found in.[1]
Similarly, for product multicommodity flow problem, we have the following extended theorem:
Theorem 5. For any directed product multicommodity flow problem with commodities,
| \Omega\left( | \varphi |
| logk |
\right)\lef\le\varphi
\varphi
The above theorems are very useful to design approximation algorithms for NP-hard problems, such as the graph partition problem and its variations. Here below we briefly introduce a few examples, and the in-depth elaborations can be found in Leighton and Rao (1999).[1]
A sparsest cut of a graph
G=(V,E)
O(logn)
O(logp)
In some applications, we want to find a small cut in a graph
G=(V,E)
b\pi(V)\le\pi(U)\le(1-b)\pi(V)
\pi(U)
O\left(Slog
| n | |
| b |
-b'\right)
| O\left( | Slogn |
| b-b' |
\right)
It is helpful to find a layout of minimum size when designing a VLSI circuit. Such a problem can often be modeled as a graph embedding problem. The objective is to find an embedding for which the layout area is minimized. Finding the minimum layout area is also NP-hard. An approximation algorithm has been introduced[1] and the result is
O(log6n)
Given an -node graph and an embedding of
Kn
Kn
O(logn)
Tragoudas[10] uses the approximation algorithm for balanced separators to find a set of
O\left((Rlogn+\sqrt{nR})log
| n | |
| R |
\right)