Difference between revisions of "Maximum flow"

Latest revision as of 03:22, 9 September 2013

The maximum flow problem is an optimization problem in graph theory. It deals with a special kind of graph, known as a flow network.

The flow network[edit]

A flow network is a directed graph with the following properties:

There are two special nodes, the source (usually denoted s), and the sink (usually denoted t).
No edges enter the source nor leave the sink.
To each edge we associate a non-negative real number called the capacity. Thus, we can represent a flow network similarly to how we would represent a weighted graph.

We may describe a flow network mathematically as a tuple $(V, s, t, c)$ where $s, t \in V$ , $c:V \times V \to [0, \infty)$ , and $\forall v, c(v, s) = c(t, v) = 0$ . Here $c(u, v)$ is the capacity of the edge from $u$ to $v$ . When we talk about an edge in a flow network, we are talking about an ordered pair of vertices $(u, v)$ for which $c(u, v) > 0$ . That is, we say that an edge exists from $u$ to $v$ if and only if $c(u, v) > 0$ .

A flow network may be used to model real-life systems in which some substance flows from one place (the source) to another (the sink), going through any number of intermediate locations (other nodes) along paths of various maximum capacities connecting locations (edges). This is the motivation behind the statement of the maximum flow problem.

Admissible flows[edit]

In order to state the maximum flow problem, we must first define the concept of an admissible flow. We have a flow network, and this flow network has a capacity function that represents, in some sense, the maximum rate at which flow can occur between a given pair of vertices. An admissible flow is an actual choice of how much flow to send between each pair of vertices. Of course, this cannot exceed the capacity. Furthermore, sending $x$ units of flow from vertex $u$ to vertex $v$ is equivalent to sending $-x$ units of flow from vertex $v$ to vertex $u$ . Finally, flow is not allowed to "accumulate" at a vertex; the amount flowing in must equal the amount flowing out.

Mathematically, an admissible flow is a function $f: V \times V \to \mathbb{R}$ such that:

Capacity constraint: $\forall u, v \in V \times V, f(u, v) \leq c(u, v)$ .
Skew symmetry: $\forall u, v \in V, f(u, v) = -f(v, u)$ .
Conservation of flow: $\forall u \in V, \sum_{v \in V} f(u, v) = 0$ .

Note that the conservation constraint is more naturally translated as $\forall u \in V, \sum_{v \in V} f(u, v) = \sum_{v \in V} f(v, u)$ based on our description above ("the amount flowing in must equal the amount flowing out"). However, as a consequence of the skew symmetry constraint, $\sum_{v \in V} f(v, u) = \sum_{v \in V} -f(u, v) = -\sum_{v \in V} f(u, v)$ . If this is to equal $\sum_{v \in V} f(u, v)$ , then this quantity must be identically zero.

An edge $(u, v)$ and its reverse edge $(v, u)$ may have different capacities. For example, if $c(u, v) = 5$ and $c(v, u) = 3$ , then we can, for example, send 4 units of flow from $u$ to $v$ and -4 units from $v$ to $u$ . (Negative flow always satisfies a capacity constraint.) We cannot send 4 units of flow from $v$ to $u$ and -4 units from $u$ to $v$ , however, because $4 > 3 = c(v, u)$ . If positive flow goes from $v$ to $u$ , we can only send up to 3 units. We also cannot send 5 units from $u$ to $v$ and 3 units from $v$ to $u$ , because this violates skew symmetry.

In the remainder of this article, flow will mean admissible flow when the context is appropriate.

Analogies[edit]

In one possible analogy, the edges represent pipes, each of which has some maximum rate at which it can transport water (the capacity). An admissible flow then corresponds to some way of sending water through the pipes from source to sink through a series of intermediate nodes. The rate at which water flows into an intermediate node must equal the rate at which water flows out of the same node, because the nodes can't store excess water, and water can't just come out of nowhere.
In another possible analogy, the edges represent conducting wires, each of which has some maximum amount of current it can conduct before it overheats and melts; the source represents a generator and the sink represents a device that consumes electrical power. Here, the balance condition is Kirchhoff's current law, stating that the total current flowing into a vertex equals the total current flowing out of it, and corresponds to the fact that any imbalance in current would result in an accumulation of either positive or negative charge at that vertex. In this analogy, the role of skew symmetry is clearer. In circuit analysis, sending a positive current from one node to another is equivalent to sending the same amount of negative current in the other direction.

Residual network[edit]

Given a flow network $(V, s, t, c)$ and a flow $f$ , we may form the residual capacity network or simply residual network $(V, s, t, r)$ . This is a new flow network in which $r(u, v) = c(u, v) - f(u, v)$ . Because $c(u, v) - f(u, v) \geq 0$ for any valid flow, $r$ is a valid capacity function (takes on nonnegative values only). The residual network may contain edges that the original network does not. In particular, if $c(u, v) > 0$ and $c(v, u) = 0$ , and we send flow from $u$ to $v$ in $f$ , that is, $f(u, v) > 0$ , then $r(v, u) = c(v, u) - f(v, u) = 0 + f(u, v) > 0$ . In other words, sending flow in one direction between two vertices can generate a back edge in the residual network. If a reverse edge already existed, then sending flow along the forward edge causes the capacity of the reverse edge to increase in the residual network.

The residual network tells us how much capacity is left in the original flow network after we've already sent some flow through it. The appearance of back edges corresponds to the fact that we are now allowed to send flow in the other direction to cancel out the existing flow. For example, if $c(u, v) = 8$ and $c(v, u) = 0$ , and $f(u, v) = 6$ , then $r(u, v) = 2$ and $r(v, u) = 6$ . We can send further flow of up to 2 units in the $u$ to $v$ direction, or we can send flow from $v$ to $u$ of up to 6 units. As long as we do not send more than 6 units in the $v$ to $u$ direction, this will just cancel out the existing flow and the total flow from $v$ to $u$ will still be less than or equal to zero, which makes the flow valid for the original network.

Statement of the problem[edit]

Given an admissible flow, although incoming flow and outgoing flow balance at all vertices other than the source and the sink, the same is not true at the source and sink. Indeed, we can have flow out from the source, but not in, since no edges enter the source; we can have flow into the sink but not out, since no edges leave the sink. The objective of the problem is to find an admissible flow that maximizes the total flow out of the source or into the sink. Such a flow is called a maximum flow.

Proposition: The total outgoing flow at the source equals the total incoming flow at the sink.

Proof: Consider the total outgoing flow at all vertices, $\sum_{u \in V} \sum_{v \in V} f(u, v)$ . This is zero by skew symmetry. Explicitly:

\sum_{u \in V} \sum_{v \in V} f(u, v)

= \sum_{u \in V} \sum_{v \in V} \frac{1}{2} (f(u, v) + f(u, v))

= \sum_{u \in V} \sum_{v \in V} \frac{1}{2} (f(u, v) - f(v, u))

= \frac{1}{2} \sum_{u \in V} \sum_{v \in V} f(u, v) - \frac{1}{2} \sum_{u \in V} \sum_{v \in V} f(v, u)

= \frac{1}{2} \sum_{u \in V} \sum_{v \in V} f(u, v) - \frac{1}{2} \sum_{u \in V} \sum_{v \in V} f(u, v)

= 0

where, between the third-to-last and second-to-last lines, we have relabelled the dummy variables $u$ and $v$ in the second term and exchanged the order of summation.

We now rewrite the original sum as $\sum_{u \in V-\{s, t\}} \sum_{v \in V} f(u, v) + \sum_{v \in V} f(s, v) + \sum_{v \in V} f(t, v)$ . The first term is zero, by the conservation constraint. The entire expression also equals zero. Therefore $\sum_{v \in V} f(s, v) = -\sum_{v \in V} f(t, v) = \sum_{v \in V} f(v, t)$ , which is what we wanted. $_\blacksquare$

This common value is called the value of the flow. This is what we wish to maximize in the maximum flow problem.

Algorithms[edit]

There are a variety of algorithms for finding a maximum flow in a flow network. The simplest are the Ford–Fulkerson method and the preflow push algorithms.

Ford–Fulkerson method[edit]

The Ford–Fulkerson method (q.v.) comprises a set of algorithms that each proceed in a series of steps, gradually building up an admissible flow until it has reached its maximum value. Each step of the algorithm takes the previous step's output, an admissible flow, as input, and produces an admissible flow of greater value, until no further refinement is possible. The input for the first step is the empty flow ( $\forall u, v \in V, f(u, v) = 0$ ), which is always admissible. The refinement is done by finding an s-t path in the flow network that can be "added" to the current admissible flow, called an augmenting path. In subsequent stages, we find an augmenting path in the residual network rather than the original network. Once an augmenting path can no longer be found in the residual network, the network is saturated with flow and the algorithm terminates.

There is flexibility in how to choose the augmenting path at each step. A simple approach is to always pick the path with the fewest edges; this gives the Edmonds–Karp algorithm. A faster and more sophisticated approach involves partitioning the graph into level sets by distance from the source and only considering paths in which each edge proceeds from a level to the next. This is called Dinic's algorithm.

Preflow push algorithms[edit]

Preflow push algorithms differ from augmenting path algorithms in that they do not maintain an admissible flow in each step, but instead maintain a preflow, in which the total flow entering a vertex is allowed to exceed the total flow exiting the vertex (but not vice versa). The algorithm begins by generating a preflow in which every edge leaving the source is saturated (so that the source's neighbours all have excess incoming flow). Each step of the algorithm then attempts to discharge some vertex's excess by pushing flow from that vertex to an adjacent vertex. Some flow will be discharged into the sink, and whatever flow cannot be discharged into the sink eventually finds its way back to the source. The algorithm terminates when the intermediate vertices have completely discharged all of their excess incoming flow, and thus an admissible flow has been found.

Other approaches[edit]

The max flow problem may be expressed as a linear program and solved using the techniques of linear programming. Here the vector to be optimized corresponds to the flow $f$ , and has one entry for each edge in the graph. Both the capacity constraints and the balance condition are linear, and may be expressed in the form $A\mathbf{x} \leq \mathbf{b}$ . The value of the flow is also a linear function of the vector $\mathbf{x}$ . Details are left as an exercise for the reader.

Even more sophisticated approaches were given by King, Rao, and Tarjan (1994) and Orlin (2012). Combining the two approaches gives a lower bound of $O(VE)$ on the general max flow problem, the best known to date.

Minimum s-t cut problem[edit]

Given a directed graph with two special nodes, the source s (with all edges outgoing) and the sink t (with all edges incoming), we can define an s-t cut as a subset of edges that, when removed from the graph, leave the sink unreachable from the source. For example, if there is no path from the source to the sink in the original graph, then the empty set is a valid s-t cut (as are all other subsets of $E$ ).

If the graph is weighted, then we may ask for a minimum s-t cut, that is, an s-t cut whose total weight (sum of the weights of the edges it comprises) is as small as possible. We will refer to such a graph as a weighted s-t graph and represent it as $(V, E, s, t, w)$ with $w:E \to [0, \infty)$ representing the edge weights. Negative-weight edges are not allowed for simplicity, but it is easy to handle them: it is always better to cut them than not to cut them, so we remove them from the graph immediately.

A common analogy is bombing enemy supply lines. Here, there is a set of one-way roads (edges) and warehouses (vertices) used to transport materials from some factory (the source) to the front lines (the sink). Each road has a certain cost to bomb (its weight), and we want to bomb enough roads to disconnect the factory from the front lines, while minimizing total cost.

For any weighted s-t graph $(V, E, s, t, w)$ , there is a corresponding flow network $(V, s, t, c)$ with the same structure. Here, $c(u, v) = w((u, v))$ if $(u, v) \in E$ , otherwise $c(u, v) = 0$ . In other words, the capacity between two vertices in the flow network is just the weight of the edge between them in the weighted s-t graph, or zero if there is no such edge.

A famous result known as the max-flow min-cut theorem demonstrates the equivalence of the maximum flow and minimum s-t cut problems. The theorem tells us that the value of a max flow in a flow network equals the total weight of a min cut in the corresponding weighted s-t graph. Because of this, there is no need to devise separate algorithms for the max flow and minimum s-t cut problems. Constructing a min cut from a max flow is straightforward and is based on the proof of the theorem. On the other hand, a max flow cannot be straightforwardly constructed from a min cut.

Variations[edit]

One or more edges in a flow network may be uncapacitated. Such an edge has unlimited capacity. We can usually handle such edges by setting their capacity to a very large value, greater than the sum of capacities of all capacitated edges in the graph. An uncapacitated edge in a flow network corresponds to an uncuttable edge in a weighted s-t graph.

Sometimes we may have to deal with a variation of a flow network in which there may be multiple sources or multiple sinks. This can be handled by adding a new "supersource" with an uncapacitated edge to each of the original sources. Likewise, we can add a new "supersink" with an uncapacitated edge from each of the original sinks.

A flow network in which there are multiple edges between a given pair of vertices can be handled by replacing the multiple edges by a single edge whose capacity equals the sum of the capacities of the original edges.

The maximum flow problem is easily solved when there are vertex capacities in addition to edge capacities. A vertex capacity $c(v)$ is the constraint that $\sum_{u \in V} \max(f(u, v), 0) \leq c(v)$ ; in other words, the total amount of incoming positive flow (or, equivalently, outgoing positive flow) cannot exceed the capacity. We can always reduce a network with vertex capacities to a network with only edge capacities and hence solve the problem using any standard max flow algorithm on the result of the reduction. To do so, we split each vertex $v$ into an "incoming vertex" $v_i$ and an "outgoing vertex" $v_o$ . Every edge $(u, v)$ in the original network is mapped to the edge $(u_o, v_i)$ in the new network (i.e., an edge leaving the outgoing vertex of $u$ and entering the incoming vertex of $v$ ) of the same capacity. Furthermore, we add an edge from $v_i$ to $v_o$ whose capacity equals the original vertex capacity $c(v)$ . In such a way, all flow that would have gone through $v$ in the original graph must now enter through $v_i$ and exit through $v_o$ , going through the edge $(v_i, v_o)$ ; a constraint on this edge therefore yields the desired result, effectively a constraint on the original vertex.

We can likewise consider the minimum s-t cut problem in which we are allowed to remove vertices (for a cost) as well as edges. The reduction is analogous: we split each vertex into an incoming vertex and an outgoing vertex, with an edge from the incoming vertex to the outgoing vertex whose weight equals the original vertex cost.

Applications[edit]

TODO

@@ Line 77: / Line 77: @@
 For any weighted s-t graph <math>(V, E, s, t, w)</math>, there is a corresponding flow network <math>(V, s, t, c)</math> with the same structure. Here, <math>c(u, v) = w((u, v))</math> if <math>(u, v) \in E</math>, otherwise <math>c(u, v) = 0</math>. In other words, the capacity between two vertices in the flow network is just the weight of the edge between them in the weighted s-t graph, or zero if there is no such edge.
-A famous result known as the ''max-flow min-cut theorem'' demonstrates the equivalence of the maximum flow and minimum s-t cut problems. The max-flow min-cut theorem follows from strong [[duality]] in linear programming, however we shall state and prove it directly below.
+A famous result known as the [[max-flow min-cut theorem]] demonstrates the equivalence of the maximum flow and minimum s-t cut problems. The theorem tells us that the value of a max flow in a flow network equals the total weight of a min cut in the corresponding weighted s-t graph. Because of this, there is no need to devise separate algorithms for the max flow and minimum s-t cut problems. Constructing a min cut from a max flow is straightforward and is based on the proof of the theorem. On the other hand, a max flow cannot be straightforwardly constructed from a min cut.
-'''Lemma 1''': Let <math>f</math> be a flow in a flow network <math>(V, s, t, c)</math>. Suppose we have a set <math>S \in V</math> such that <math>s \in S</math> and <math>t \notin S</math>. Then the value of the flow <math>\sum_{v \in S} f(s, v)</math> equals the total flow leaving <math>S</math>, <math>\sum_{u \in S} \sum_{v \notin S} f(u, v)</math>.
-'''Proof''':
-:<math>\sum_{u \in S} \sum_{v \notin S} f(u, v)</math>
-:<math>= \sum_{u \in S} \sum_{v \in V} f(u, v) - \sum_{u \in S} \sum_{v \in S} f(u, v)</math>
-:<math>= \sum_{u \in S} \sum_{v \in V} f(u, v)</math> ''(by skew symmetry)''
-:<math>= \sum_{u \in S-\{s\}} \sum_{v \in V} f(u, v) + \sum_{v \in V} f(s, v)</math>
-:<math>= \sum_{v \in V} f(s, v)</math> ''(by flow conservation)'' <math>_\blacksquare</math>
-'''Lemma 2''': Let <math>f</math> be a flow in a flow network <math>(V, s, t, c)</math>. Let <math>C</math> be an s-t cut in the corresponding weighted s-t graph <math>(V, E, s, t, w)</math>. Then the value of <math>f</math>, <math>\sum_{v \in V} f(s, v)</math>, is less than or equal to the total weight of <math>C</math>, <math>\sum_{e \in C} w(e)</math>.
-'''Proof''': Since <math>C</math> is an s-t cut, in the weighted s-t graph <math>(V, E \setminus C, s, t, w)</math>, there is no path from <math>s</math> to <math>t</math>. We can therefore consider the set <math>S</math> of all vertices reachable from <math>s</math> in this graph. Note that <math>t \notin S</math>. Applying Lemma 1, we find that <math>\sum_{v \in S} f(s, v) = \sum_{u \in S} \sum_{v \notin S} f(u, v) \leq \sum_{u \in S} \sum_{v \notin S} c(u, v) = \sum_{e \in C'} w(e)</math>. <math>_\blacksquare</math>
-The intuition behind the Lemmata and their proofs is that, if we cut the graph, then all the flow coming out of the source has to get from nodes in <math>S</math> to nodes in <math>V\setminus S</math> at some point, and it can only do so by flowing out through edges between <math>S</math> and <math>V\setminus S</math>. The total amount of flow cannot therefore exceed the total capacity of such edges, which is the same as the total weight of the cut.
-We are now ready to state and prove the main result of this section.
-'''Theorem (Max-flow min-cut theorem)''': Let <math>f</math> be a maximum flow in a flow network <math>(V, s, t, c)</math>. Consider the set <math>S \subset V</math> consisting of vertices reachable from <math>s</math> in the residual network corresponding to <math>f</math>. A minimum s-t cut of the corresponding weighted s-t graph <math>(V, E, s, t, w)</math> is given by <math>C = \{e = (u, v) \mid e \in E, u \in S, v \notin S \}</math>. Furthermore, the value of the max flow <math>\sum_{v \in V} f(s, v)</math> equals the value of the min cut <math>\sum_{e \in C} w(e)</math>.
-'''Proof''': It suffices to show that <math>\sum_{v \in V} f(s, v) = \sum_{e \in C} w(e)</math>. The fact that the cut <math>C</math> is minimal then follows immediately from Lemma 2.
-Since the flow <math>f</math> is maximal, there is no [[augmenting path]] in the residual network <math>(V, s, t, r)</math>. Therefore, <math>t \notin S</math>. Now, <math>r(u, v) = 0</math> for all <math>u \in S</math> and <math>v \notin S</math>, by definition of <math>S</math>. Therefore, <math>c(u, v) = f(u, v)</math> for all such edges. By Lemma 1, <math>\sum_{v \in V} f(s, v) = \sum_{u \in S} \sum_{v \notin S} f(u, v) = \sum_{u \in S} \sum_{v \notin S} c(u, v) = \sum_{e \in C} w(e)</math>. <math>_\blacksquare</math>
-In other words, we can solve the minimum s-t cut problem simply by converting all the edge weights to capacities and then finding a maximum flow in the resulting flow network. If we only want the weight of the min cut, we can simply find the value of the max flow, and be done with it. If we want to find the cut explicitly, then it is still straightforward to do so using the residual graph corresponding to the max flow. The "s part" of the s-t cut will consist of vertices reachable from <math>s</math> in the residual graph, with the remainder the "t part". The edges we want to cut are the ones from the "s part" to the "t part".
 ==Variations==

Difference between revisions of "Maximum flow"

Latest revision as of 03:22, 9 September 2013

Contents

The flow network[edit]

Admissible flows[edit]

Analogies[edit]

Residual network[edit]

Statement of the problem[edit]

Algorithms[edit]

Ford–Fulkerson method[edit]

Preflow push algorithms[edit]

Other approaches[edit]

Minimum s-t cut problem[edit]

Variations[edit]

Applications[edit]

Navigation menu

Personal tools

Namespaces

Variants

Views

More

Search

Navigation

Tools