Maximum flow - Revision history

Brian: /* Minimum s-t cut problem */

2013-09-09T03:22:11Z

‎Minimum s-t cut problem

Brian: /* Minimum s-t cut problem */ - typo, used wrong symbol

2013-09-09T02:24:50Z

‎Minimum s-t cut problem: - typo, used wrong symbol

Brian: /* Minimum s-t cut problem */

2013-09-09T00:27:05Z

‎Minimum s-t cut problem

Brian at 00:17, 9 September 2013

2013-09-09T00:17:17Z

Show changes

Brian: in progress

2013-09-07T20:57:49Z

in progress

Brian: in progress

2013-09-07T02:06:07Z

in progress

New page

The '''maximum flow problem''' is an optimization problem in [[graph theory]]. It deals with a special kind of graph, known as a ''flow network''. 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.
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.

In order to state the problem, we first have to define the concept of an ''admissible flow''. An admissible flow is an assignment of a non-negative real number to each edge (which we call the ''flow along'' that edge) such that the flow along an edge never exceeds the capacity of that edge, and such the flow "balances" at each vertex other than the source and sink, meaning that the total flow at incoming edges equals the total flow at outgoing edges at each vertex.

The balance condition may be thought of as a precise statement of the idea that the vertices have no capacities of their own; they serve only as connecting points for the edges and cannot store excess incoming flow nor discharge stored flow when the incoming flow is running low. 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.

@@ 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 \subset 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==

@@ Line 79: / Line 79: @@
 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.
-'''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>.
+'''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 \subset 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''':

@@ Line 100: / Line 100: @@
 '''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>
+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".

@@ Line 1: / Line 1: @@
-The '''maximum flow problem''' is an optimization problem in [[graph theory]]. It deals with a special kind of graph, known as a ''flow network''. A flow network is a [[directed graph]] with the following properties:
+The '''maximum flow problem''' is an optimization problem in [[graph theory]]. It deals with a special kind of graph, known as a ''flow network''.
 # 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.
 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.
-In order to state the problem, we first have to define the concept of an ''admissible flow''. An admissible flow is an assignment of a non-negative real number to each edge (which we call the ''flow along'' that edge) such that the flow along an edge never exceeds the capacity of that edge, and such the flow "balances" at each vertex other than the source and sink, meaning that the total flow at incoming edges equals the total flow at outgoing edges at each vertex.
+==Admissible flows==
-The balance condition may be thought of as a precise statement of the idea that the vertices have no capacities of their own; they serve only as connecting points for the edges and cannot store excess incoming flow nor discharge stored flow when the incoming flow is running low. 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.
+Even more sophisticated approaches were given by King, Rao, and Tarjan (1994) and Orlin (2012). Combining the two approaches gives a lower bound of <math>O(VE)</math> on the general max flow problem, the best known to date.