Max-flow min-cut theorem

From Wikipedia, the free encyclopedia

The max-flow min-cut theorem is a statement in optimization theory about maximum flows in flow networks. It derives from Menger's theorem. It states that:

The maximum amount of flow is equal to the capacity of a minimal cut.

In other words, the theorem states that the maximum flow in a network is dictated by its bottleneck. Between any two nodes, the quantity of material flowing from one to the other cannot be greater than the weakest set of links somewhere between the two nodes.

Contents

[edit] Definition

Suppose G(V,E) is a finite directed graph and every edge (u,v) has a capacity c(u,v) (a non-negative real number). Further assume two vertices, the source s and the sink t, have been distinguished.

Main article: Cut (graph theory)

A cut is a split of the nodes into two sets S and T, such that s is in S and t is in T. Hence there are

2^{|V|-2}\,

possible cuts in a graph. The capacity of a cut (S,T) is

c(S,T) = \sum_{u \in S, v \in T | (u,v) \in E} c(u,v),

the sum of the capacity of all the edges crossing the cut, from the region S to the region T.

The following three conditions are equivalent:

  1. f is a maximum flow in G
  2. The residual network Gf contains no augmenting paths.
  3. | f | = c(S,T) for some cut (S,T).

Proof Sketch: If there is an augmenting path, we can send flow along it, and get a greater flow, hence it cannot be maximal, and vice versa. If there is no augmenting path, divide the graph into S, the nodes reachable from s in the residual network, and T, those not reachable. Then c(S,T) must be 0. If it is not, there is an edge (u,v) with c(u,v) > 0. But then v is reachable from s, and cannot be in T.

In particular this proves that \mathrm{max\ flow} >= \mathrm{min\ cut}, because a minimal cut is smaller or equal to the cut corresponding to our \mathrm{max\ flow}.

Then we have \mathrm{min\ cut} >= \mathrm{max\ flow}. If we have a flow f for a given graph G, removing an edge (u,v) of capacity c changes f in at least f − c, because no more than a capacity of c can be used by the flow f. But if we remove all edges cut by a given minimal cut c0, we get a flow 0, whatever the flow f we have at first. So f − c0 < = 0 for any flow f, in particular if f is a max flow. Which shows f < = c0.

[edit] Linear Program

The max-flow min-cut problem can be easily expressed as a pair of primal-dual linear programs. The following linear program computes the max flow between nodes S and T in graph G=(V, E), where V is the set of nodes and E is the set of edges. The capacity of any edge \overrightarrow{uv}\in E is represented by c(\overrightarrow{uv}). The linear program assumes the graph to be directed. The linear program for the undirected case can be easily derived from the same.

[edit] Primal (Max flow linear program)

Maximize

\qquad\mathbf{f(\overrightarrow{TS})}

Subject To

\sum_{\overrightarrow{vu}\in E} f(\overrightarrow{vu}) - \sum_{\overrightarrow{uv}\in E} f(\overrightarrow{uv}) = 0 \qquad \forall u \in V\neq {S, T} \qquad \leftrightarrow p(u)
\sum_{\overrightarrow{vT}\in E} f(\overrightarrow{vT}) - \sum_{\overrightarrow{Tv}\in E} f(\overrightarrow{Tv}) - f(\overrightarrow{TS}) = 0 \qquad \leftrightarrow p(T)
\sum_{\overrightarrow{vS}\in E} f(\overrightarrow{vS}) + f(\overrightarrow{TS}) - \sum_{\overrightarrow{Sv}\in E} f(\overrightarrow{Sv}) = 0 \qquad \leftrightarrow p(S)
f(\overrightarrow{uv}) \leq c(\overrightarrow{uv}) \qquad \forall \overrightarrow{uv}\in E \qquad \leftrightarrow x(\overrightarrow{uv})

Bounds

f(\overrightarrow{uv}) \geq 0 \qquad \forall \overrightarrow{uv} \in E, \quad f(\overrightarrow{TS}) \geq 0


Primal Explanation: The linear program computes the max flow in the variable f(\overrightarrow{TS}). \overrightarrow{TS} is a conceptual link. As there is flow conservation (flow in equals flow out) at every node, the more flow that is on this conceptual link, the more will be the flow between the source and the destination. The first constraint specifies the flow conservation at every node except the source and the destination. The second and third constraints are special flow conservation constraints for the destination and the source respectively. The final constraint limits the maximum flow on the edge to its capacity. The variable shown right at the end of every constraint is the corresponding dual variable.
An interesting fact about the above linear program is that the constraint matrix is totally unimodular. This means that, if all the inputs are integral, there exists as an integral solution. So, if all the capacities in the graph are integral, the max flow is integral.


[edit] Dual (Min cut linear program)

Minimize

\mathbf{\sum_{\overrightarrow{uv} \in E} c(\overrightarrow{uv}) . x(\overrightarrow{uv})}

Subject To

p(v) - p(u) + x(\overrightarrow{uv}) \geq 0 \qquad \forall \overrightarrow{uv} \in E \qquad \leftrightarrow f(\overrightarrow{uv})
p(S) - p(T) \geq 1 \qquad \leftrightarrow f(\overrightarrow{TS})

Bounds

p(u) free \quad \forall u, x(\overrightarrow{uv}) \geq 0 \quad \forall \overrightarrow{uv}


Dual explanation: The dual can be written mechanically from the primal based on the duality theorem in linear programming. In the dual, the variable x(\overrightarrow{uv}) decides whether an edge is a cut edge are not. The edges for which x(\overrightarrow{uv})>0 are part of the min cut and the edges for which it is 0 are not part of the cut edge. The nodes in the graph that are along with the node S after the cut can be considered to be one partition and the nodes in the graph that are with the node T can be considered to be another partition. The constraints represent the relationship between the nodes in different sets. To illustrate this, consider an example where the solution is such that the value of p for the nodes in the partition containing S is 0 and 1 otherwise. It is now obvious to see that the the value of x for the cut edges is 1 and for the rest it is 0. This will also help in understanding the meaning of the constraints. Finally, as in the primal, the variable shown right at the end of every constraint is the corresponding primal variable.
One of the interesting relationships between the primal and dual is that the objective value of optimal solutions for the primal and the dual are exactly same. Thus, since the objective value of the primal is integral, the dual will also have an integral objective value. Thus, if all the input capacities are integral, the min cut is integral.

[edit] Example

A network with maximal flow, and three minimal cuts.
A network with maximal flow, and three minimal cuts.

Given to the right is a network with nodes V = {s,o,p,q,r,t}, and a total flow from the source s to the sink t of 5, which is maximal in this network. (Incidentally, this is the only maximal flow you can assign to this network.)

There are three minimal cuts in this network:

Cut Capacity
S = {s,p},T = {o,q,r,t} c(s,o) + c(p,r) = 3 + 2 = 5
S = {s,o,p},T = {q,r,t} c(o,q) + c(p,r) = 3 + 2 = 5
S = {s,o,p,q,r},T = {t} c(q,t) + c(r,t) = 2 + 3 = 5

Notice that S = {s,o,p,r},T = {q,t} is not a minimal cut, even though both (o,q) and (r,t) are saturated in the given flow. This is because in the residual network Gf, there is an edge (r,q) with capacity cf(r,q) = c(r,q) − f(r,q) = 0 − ( − 1) = 1.

[edit] History

The theorem was proved by P. Elias, A. Feinstein, and C.E. Shannon in 1956, and independently also by L.R. Ford, Jr. and D.R. Fulkerson in the same year. Determining maximum flows is a special kind of linear programming problem, and the max flow min cut theorem can be seen as a special case of the duality theorem for linear programming.

[edit] See also

[edit] External links

[edit] References