Approximate max-flow min-cut theorem

Muticommodity flow problem

A commodity is a pair of source and sink nodes in a network flow problem. For detailed definition of multicommodity flow problem, see Multi-commodity flow problem. In a multicommodity flow problem, there are k≥1 commodities, each with its own source $s_{i}$, sink $t_{i}$, and demand $D_{i}$. The objective is to simultaneously route $D_{\text{i}}$ units of commodity i from $s_{i}$ to $t_{i}$ for each i, such that the total amount of all commodities passing through any edge is no greater than its capacity. (In the case of undirected edges, the sum of the flows in both directions can't exceed the capacity of the edge.).^[1] Specially, a 1-commodity (or single commodity) flow problem is also known as a maximum flow problem (see Maximum flow problem). According to the famous Ford–Fulkerson algorithm (see Ford–Fulkerson algorithm),the max-flow and min-cut are always equal in a 1-commodity flow problem.

Max-flow and min-cut

In a multicommodity flow problem, max-flow is the maximum value of f, where f is the common fraction of each commodity that is routed, such that $fD_{\text{i}}$ units of commodity i can be simultaneously routed for each i without violating any capacity constraints. min-cut is the minimum of all cuts of the ratio $\varphi$ of the capacity of the cut to the demand of the cut. Max-flow is always upper bounded by the min-cut for a multicommodify flow problem.

Uniform multicommodity flow problem

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]

Product multicommodity flow problem

In a product multicommodity flow problem, there is a nonnegative weight for each node $v \in V$ in graph $G=(V,E)$. The demand for the commodity between nodes u and v is the product of the weights of node u and node v. The uniform multicommodity flow problem is a special case of the product multicommodity flow problem for which the weight is set to 1 for all nodes $u \in V$.^[1]

Duality of linear programming

In general, the dual of a multicommodity flow problem for a graph G is the problem of apportioning a fixed amount of weight (where weights can be considered as distances) to the edges of G such that to maximize the cumulative distance between the source and sink pairs.^[1] (See Linear programming for detailed introduction of the duality of linear programming.)

History

The research on the relationship between the max-flow and min-cut of multicommodity flow problem has obtained great interest since Ford and Fulkterson'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 k of the min-cut since each commodity can be optimized separately using $1/k$ of the capacity of each edge. This is not a good result especially in case of large numbers of commodities.^[1]

Approximate max-flow min-cut theorems

Theorems of uniform multicommodity flow problems

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 n, there is an n-node uniform multicommodity flow problem with max-flow f and min-cut $\varphi$ for which $f\le O\left(\frac{\varphi}{\log n}\right)$.^[1]

Theorem 2. For any uniform multicommodity flow problem, $\Omega\left(\frac{\varphi}{\log n}\right)\le f\le\varphi$, where f is the max-flow and $\varphi$ is the min-cut of the uniform multicommodity flow problem.^[1]

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.

Generalized to product multicommodity flow problem

Theorem 3. For any product multicommodity flow problem with k commodities, $\Omega\left(\frac{\varphi}{\log k}\right)\le f\le \varphi$, where f is the max-flow and $\varphi$ is the min-cut of the product multicommodity flow problem. ^[1]

The proof methodology is similar as it is for Theorem 2, the major difference is to take node weights into consideration.

Extended to directed multicommodity flow problem

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 n nodes, $\Omega\left(\frac{\varphi}{\log n}\right)\le f\le \varphi$, where f is the max-flow and $\varphi$ is the min-cut of the uniform multicommodity flow problem. ^[1]

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 k commodities, $\Omega\left(\frac{\varphi}{\log k}\right)\le f\le\varphi$, where f is the max-flow and $\varphi$ is the directed min-cut of the product multicommodity flow problem. ^[1]

Applications to approximation algorithms

The above theorems are very useful to design approximation algorithms (see Approximation algorithm) for NP-hard problems (see NP-hard), such as the graph partition problem and its variations (see Graph partition). Here below we briefly introduce a few examples, and the in-depth elaborations can be found in:^[1]

Sparsest cuts

A sparsest cut of a graph $G=(V,E)$ is a partition for which the ratio of the number of edges connecting the two partitioned components over the product of the numbers of nodes of both components. This is a NP-hard problem, and it can be approximated to within $O(\log n)$ factor using Theorem 2. Also, a sparsest cut problem with weighted edges, weighted nodes or directed edges can be approximated within an $O(\log p)$ factor where p is the number of nodes with nonzero weight according to Theorem 3, 4 and 5.

Balanced cuts and separators

In some applications, we want to find a small cut in a graph $G=(V,E)$ that partitions the graph into nearly equal-size pieces. We usually call a cut b-balanced or a (b,1 − b)-separator (for b ≤ 1/2) if $b\pi(V)\le\pi(U)\le(1-b)\pi(V)$ where $\pi(U)$ is the sum of the node weights in U. This is also an NP-hard problem. In,^[1] there is an approximation algorithm designed for this problem, and the core idea is that G has a b-balanced cut of size S, then we find a b′-balanced cut of size $O\left(S\log \frac n b -b'\right)$ for any b' where b′ < b and b′ ≤ 1/3. Then repeat the process then finally obtain the total weight of the edges in the cut is at most $O\left(\frac{S\log n}{b-b'}\right)$.

VLSI layout problems

It's helpful to find a layout of minimum size when designing a VLSI circuit, such 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 is introduced in ^[1] and the result is $O(\log^6 n)$ times optimal.

Forwarding index problem

Given an n-node graph G and an embedding of $K_n$ in G, Chung et al. ^[9] defined the forwarding index of the embedding to be the maximum number of paths (each corresponding to an edge of $K_n$) that pass through any node of G. The objective is to find an embedding that minimizes the forwarding index. According to the embedding approaches introduced in,^[1] it is possible to bound the node and edge-forwarding indices to within an $O(\log n)$-factor for every graph G.

Planar edge deletion

Tragoudas^[10] uses the approximation algorithm for balanced separators to find a set of $O\left((R\log n + \sqrt{nR})\log\frac{n}{R}\right)$ edges whose removal from a bounded-degree graph G results in a planar graph, where R is the minimum number of edges that need to be removed from G before it becomes planar. It remains an open question if there is a polylog n times optimal approximation algorithm for R.^[1]

See also

• Multi-commodity flow problem
• Linear programming
• Ford–Fulkerson algorithm
• Max-flow min-cut theorem
• Maximum flow problem
• Minimum cut
• Flow network
• Approximation algorithm
• NP-hard
• Graph partition

References

1. LEIGHTON, TOM; RAO, SATISH (November 1999). "Multicommodity Max-Flow Min-Cut Theorems and Their Use in Designing Approximation Algorithms". Journal of the ACM 46 (6): 787–832. doi:10.1145/331524.331526.
2. HU, T.C. (1963). "Multicommodity network flows". Oper. Res. 11 (3): 344–360.
3. OKAMURA, H.; SEYMOUR, P.D. (1981). "Multicommodity flows in planar graphs". J. Combin. Theory, Ser. B (31): 75–81.
4. SHAHROKHI, F.; MATULA, D.W. (1990). "The maximum concurrent flow problem". J. ACM 37: 318–334. doi:10.1145/77600.77620.
5. KLEIN, P.; PLOTKIN, S.; RAO, S.; TARDOS, E. (1997). "Bounds on the max-flow min-cut ratio for directed multicommodity flows". J. Algorithms 22: 241–269.
6. GARG, N.; VAZARANI, V.; YANNAKAKIS, M. (1996). "Approximate max-flow min-(multi)cut theorems and their applications". SIAM J. Comput. 25: 235–251. doi:10.1137/s0097539793243016.
7. PLOTKIN, S.; TARDOS, E. (1993). "Improved bounds on the max-flow min-cut ratio for multicommodity flows". In Proceedings of the 25th Annual ACM Symposium on Theory of Computing: 691– 697.
8. LEIGHTON, TOM; RAO, SATISH (1988). "An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms". Proc.29th IEEE Symposium on Foundations of Computer Science: 422–431.
9. CHUNG, F. K.; COFFMAN, E. G.; REIMAN, M. I.; SIMON, B. E. (1987). "The forwarding index of communication networks". IEEE Trans. Inf. Theory 33: 224–232. doi:10.1109/tit.1987.1057290.
10. TRAGOUDAS, S. (1990). "VLSI partitioning approximation algorithms based on multicommodity flows and other techniques". Ph.D. dissertation. Dept. Comput. Sci., Univ. Texas.