Approximate max-flow min-cut theorem

Last updated January 05, 2024

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.

Multicommodity flow problem
Max-flow and min-cut
Uniform multicommodity flow problem
Product multicommodity flow problem
Duality of linear programming
History
Approximate max-flow min-cut theorems
Theorems of uniform multicommodity flow problems
Generalized to product multicommodity flow problem
Extended to directed multicommodity flow problem
Applications to approximation algorithms
Sparsest cuts
Balanced cuts and separators
VLSI layout problems
Forwarding index problem
Planar edge deletion
References

Multicommodity flow problem

A "commodity" in a network flow problem is a pair of source and sink nodes. In a multi-commodity flow problem, there are $k\geq1$ 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 cannot exceed the capacity of the edge).^[1] Specially, a 1-commodity (or single commodity) flow problem is also known as a maximum flow problem. According to the 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 multicommodity 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]

History

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 $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\leq O\left({\frac {\varphi }{\log n}}\right)$ .^[1]

Theorem 2.For any uniform multicommodity flow problem, $\Omega \left({\frac {\varphi }{\log n}}\right)\leq f\leq \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)\leq f\leq \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 to that 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)\leq f\leq \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)\leq f\leq \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 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]

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 is minimized. 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 \leq 1/2$ ) if $b\pi (V)\leq \pi (U)\leq (1-b)\pi (V)$ where $\pi (U)$ is the sum of the node weights in $U$ . This is also an NP-hard problem. An approximation algorithm has been designed for this problem,^[1] 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' \leq 1/3$ . Then we repeat the process then finally obtain the result that total weight of the edges in the cut is at most $O\left({\frac {S\log n}{b-b'}}\right)$ .

VLSI layout problems

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(\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. Using embedding approaches^[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]

Related Research Articles

In graph theory, an expander graph is a sparse graph that has strong connectivity properties, quantified using vertex, edge or spectral expansion. Expander constructions have spawned research in pure and applied mathematics, with several applications to complexity theory, design of robust computer networks, and the theory of error-correcting codes.

<span class="mw-page-title-main">Euler's totient function</span> Number of integers coprime to and not exceeding n

In number theory, Euler's totient function counts the positive integers up to a given integer $n$ that are relatively prime to $n$ . It is written using the Greek letter phi as $or, and may also be called Euler's phi function . In other words, it is the number of integers k in the range 1 \leq k \leq n for which the greatest common divisor gcd(n, k) is equal to 1. The integers k of this form are sometimes referred to as totatives of n .$

In computer science and optimization theory, the max-flow min-cut theorem states that in a flow network, the maximum amount of flow passing from the source to the sink is equal to the total weight of the edges in a minimum cut, i.e., the smallest total weight of the edges which if removed would disconnect the source from the sink.

In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices are of the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color.

In mathematics, specifically the study of differential equations, the Picard–Lindelöf theorem gives a set of conditions under which an initial value problem has a unique solution. It is also known as Picard's existence theorem, the Cauchy–Lipschitz theorem, or the existence and uniqueness theorem.

In graph theory, a cut is a partition of the vertices of a graph into two disjoint subsets. Any cut determines a cut-set, the set of edges that have one endpoint in each subset of the partition. These edges are said to cross the cut. In a connected graph, each cut-set determines a unique cut, and in some cases cuts are identified with their cut-sets rather than with their vertex partitions.

In graph theory, a minimum cut or min-cut of a graph is a cut that is minimal in some metric.

The Remez algorithm or Remez exchange algorithm, published by Evgeny Yakovlevich Remez in 1934, is an iterative algorithm used to find simple approximations to functions, specifically, approximations by functions in a Chebyshev space that are the best in the uniform norm L_∞ sense. It is sometimes referred to as Remes algorithm or Reme algorithm.

In computer science and graph theory, Karger's algorithm is a randomized algorithm to compute a minimum cut of a connected graph. It was invented by David Karger and first published in 1993.

In mathematics, the super-logarithm is one of the two inverse functions of tetration. Just as exponentiation has two inverse functions, roots and logarithms, tetration has two inverse functions, super-roots and super-logarithms. There are several ways of interpreting super-logarithms:

In graph theory the conductance of a graph $G = (V, E)$ measures how "well-knit" the graph is: it controls how fast a random walk on $G$ converges to its stationary distribution. The conductance of a graph is often called the Cheeger constant of a graph as the analog of its counterpart in spectral geometry. Since electrical networks are intimately related to random walks with a long history in the usage of the term "conductance", this alternative name helps avoid possible confusion.

In graph theory, the planar separator theorem is a form of isoperimetric inequality for planar graphs, that states that any planar graph can be split into smaller pieces by removing a small number of vertices. Specifically, the removal of vertices from an $n$ -vertex graph can partition the graph into disjoint subgraphs each of which has at most vertices.

<span class="mw-page-title-main">Maximum cut</span> Problem of finding a maximum cut in a graph

In a graph, a maximum cut is a cut whose size is at least the size of any other cut. That is, it is a partition of the graph's vertices into two complementary sets $S$ and $T$ , such that the number of edges between $S$ and $T$ is as large as possible. Finding such a cut is known as the max-cut problem.

In mathematics, the ATS theorem is the theorem on the approximation of a trigonometric sum by a shorter one. The application of the ATS theorem in certain problems of mathematical and theoretical physics can be very helpful.

David Bernard Shmoys is a Professor in the School of Operations Research and Information Engineering and the Department of Computer Science at Cornell University. He obtained his Ph.D. from the University of California, Berkeley in 1984. His major focus has been in the design and analysis of algorithms for discrete optimization problems.

In graph theory, the graph bandwidth problem is to label the $n$ vertices $v i$ of a graph $G$ with distinct integers so that the quantity $is minimized . The problem may be visualized as placing the vertices of a graph at distinct integer points along the x -axis so that the length of the longest edge is minimized. Such placement is called linear graph arrangement, linear graph layout or linear graph placement .$

In graph theory, the Lovász number of a graph is a real number that is an upper bound on the Shannon capacity of the graph. It is also known as Lovász theta function and is commonly denoted by $, using a script form of the Greek letter theta to contrast with the upright theta used for Shannon capacity. This quantity was first introduced by László Lovász in his 1979 paper On the Shannon Capacity of a Graph .$

In theoretical computer science and metric geometry, the GNRS conjecture connects the theory of graph minors, the stretch factor of embeddings, and the approximation ratio of multi-commodity flow problems. It is named after Anupam Gupta, Ilan Newman, Yuri Rabinovich, and Alistair Sinclair, who formulated it in 2004.

Satish B. Rao is an American computer scientist who is a professor of computer science at the University of California, Berkeley.

In graph theory, the cutwidth of an undirected graph is the smallest integer $with the following property: there is an ordering of the vertices of the graph, such that every cut obtained by partitioning the vertices into earlier and later subsets of the ordering is crossed by at most edges. That is, if the vertices are numbered, then for every, the number of edges with and is at most .$

References

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 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. CiteSeerX 10.1.1.640.2995 . doi:10.1145/331524.331526. S2CID 18527968.
↑ Hu, T. C. (1963). "Multicommodity network flows". Operations Research . 11 (3): 344–360. doi:10.1287/opre.11.3.344.
↑ Okamura, H.; Seymour, P. D. (1981). "Multicommodity flows in planar graphs". Journal of Combinatorial Theory, Series B . 31: 75–81. doi:10.1016/S0095-8956(81)80012-3.
↑ Shahrokri, F.; Matula, David W. (1990). "The maximum concurrent flow problem". Journal of the ACM . 37 (2): 318–334. doi: 10.1145/77600.77620 . S2CID 4469579.
↑ 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.
1 2 Garg, N.; Vazarani, V.; Yannakakis, M. (1996). "Approximate max-flow min-(multi)cut theorems and their applications". SIAM Journal on Computing . 25 (2): 235–251. doi:10.1137/s0097539793243016.
↑ Plitkin, S.; Tardos, E. (1993). "Improved bounds on the max-flow min-cut ratio for multicommodity flows". Proceedings of the 25th Annual ACM Symposium on Theory of Computing: 691–697.
↑ Leighton, Tom; Rao, Satish (1988). "An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms". Proceedings of the 29th IEEE Symposium on Foundations of Computer Science: 422–431.
↑ Chung, F. K.; Coffman, E. G.; Reiman, M. I.; Simon, B. E. (1987). "The forwarding index of communication networks". IEEE Transactions on Information Theory . 33 (2): 224–232. doi:10.1109/tit.1987.1057290.
↑ Tragoudas, S. (1990). VLSI partitioning approximation algorithms based on multicommodity flows and other techniques (Ph.D. dissertation). Department of Computer Sciences, University of Texas.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[Leighton99-1] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 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. CiteSeerX 10.1.1.640.2995 . doi:10.1145/331524.331526. S2CID 18527968.

[hu63-2] Hu, T. C. (1963). "Multicommodity network flows". Operations Research . 11 (3): 344–360. doi:10.1287/opre.11.3.344.

[Okamura_and_Seymour_81-3] Okamura, H.; Seymour, P. D. (1981). "Multicommodity flows in planar graphs". Journal of Combinatorial Theory, Series B . 31: 75–81. doi:10.1016/S0095-8956(81)80012-3.

[Shahrokhi_and_Matula_90-4] Shahrokri, F.; Matula, David W. (1990). "The maximum concurrent flow problem". Journal of the ACM . 37 (2): 318–334. doi: 10.1145/77600.77620 . S2CID 4469579.

[Klein97-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.

[Garg96-6] 1 2 Garg, N.; Vazarani, V.; Yannakakis, M. (1996). "Approximate max-flow min-(multi)cut theorems and their applications". SIAM Journal on Computing . 25 (2): 235–251. doi:10.1137/s0097539793243016.

[Plotkin_and_Tardos_93-7] Plitkin, S.; Tardos, E. (1993). "Improved bounds on the max-flow min-cut ratio for multicommodity flows". Proceedings of the 25th Annual ACM Symposium on Theory of Computing: 691–697.

[Leighton88-8] Leighton, Tom; Rao, Satish (1988). "An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms". Proceedings of the 29th IEEE Symposium on Foundations of Computer Science: 422–431.

[CHUNG87-9] Chung, F. K.; Coffman, E. G.; Reiman, M. I.; Simon, B. E. (1987). "The forwarding index of communication networks". IEEE Transactions on Information Theory . 33 (2): 224–232. doi:10.1109/tit.1987.1057290.

[TRAGOUDAS90-10] Tragoudas, S. (1990). VLSI partitioning approximation algorithms based on multicommodity flows and other techniques (Ph.D. dissertation). Department of Computer Sciences, University of Texas.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]