We discussed how to formulate the MAXFLOW problem for networks, i.e. arc-weighted digraphs with two specific vertices, source and sink and arc capacities , and treat it via linear programming. An alternative approach is via augmenting paths. The paths we talk about will disregard the arc directions in , i.e. they will be – paths in the underlying undirected graph. (When has the direction opposite to the arc in , we write .)
Definition 1 Given an – flow , an –augmenting path is an – path in the underlying graph, such that for each
- if then ;
- if then .
The tolerance of is
Note that the definition of tolerance extends unchanged to any path starting at .
We can use to improve , as follows.
Lemma 2 For each , let
Then is an – flow in , of value greater than that of by
Proof: It is immediate from the definition of that for any . We still need to check the flow conservation constraints
If visits then there are two arcs, say, and on that are affected when we change to , and the changes in flow values cancel each other in each of the four cases (recall that is a path in the underlying undirected graph). Finally, the value of is the net outflow from , and the latter is greater than that of by .
This suggests finding a maximum flow by repeatedly finding an augmenting path and improving the current flow with it, till no augmenting path is available (this is, for instance, how Ford-Fulkerson algorithm is working). For this to succeed, we obviously need to prove that is maximum if and only if it does not have an -augmenting path.
Augmenting paths are found by a breadth-first search from . At some point, if we did not succeed in reaching , we would end up with the set of vertices reachable, in the underlying non-oriented graph, by paths with positive tolerance. Each crossing over from to satisfies the property that , and each arc crossing from to satisfies — otherwise we would have added their vertices in to . Therefore,
where on the right we have the definition of capacity of an arbitrary – cut .
It is easy to show that for an arbitrary – cut , one has . Thus we have have obtained the Maxflow-Mincut Theorem, and also proved that our algorithm, to be described in more detail shortly, finds a maximum flow , and a corresponding to it minimum cut .
Breadth-first search: Ford-Fulkerson algorithm
As usual in breadth-first search, we use a queue, i.e. a data structure that has two indices, one, , pointing to the end of the queue, for new arrivals, and the other, , pointing to the beginning of the queue, i.e. to the first element to be processed. There will be elementary operations:
- – adds a new element, , to the queue, and icrements . In this case we also do not allow an element to enter the queue twice, so has no effect if already was these once.
- – takes the (currently) first element, , from the queue, and icrements —this will fail if is empty, i.e. if .
Now the algorithm is as follows:
- Input: a feasible flow in with source and sink .
- Initialization: let be an empty queue; , and set .
- Loop: take . If this fails, return the first coordinates of the pairs in —a minimum cut.
- for s.t. and , or s.t. and :
- , .
- if then return the augmenting – path by tracing back the pairs , ,\dots, in .
- go to Loop.
So if is not maximum we get an -augmenting path, that can be used to improve , and repeat. However, the speed of this procedure becomes unacceptable when the capacities are large. If then we are at least assured that it will converge after finitely many steps: indeed, we can multiply by the least common multiple of its denominators, reducing to the case . Each iteration in this case improves the flow by at least . However, the time would not be polynomial in the input of the problem. E.g. for the following graph the number of iterations can be as large as , when is a large integer.
For irrational the convergence not even need to be the case!
If one chooses a shortest -augmenting path to improve with, then the running time becomes bounded by —that was shown by E.Dinitz in 1970 and independently by J.Edmonds and R.Karp in 1972. Details, and further improvements by A.Karzanov et.al can be found e.g. in A.Schrijver’s lecture notes, Sect.4.4.
Tags: graph theory, MAS324
5 November, 2010 at 16:53 |
It would be nice to show an example with irrational capacities and an infinite sequence of augmenting paths.
5 November, 2010 at 18:20 |
If you want to write up such an example, I could include it in the post…
5 November, 2010 at 18:52 |
Actually, while Googling for such an example I found this Dima’s web-page.
Meanwhile I found an example in section 6.3 (pages 126-128) of:
Combinatorial Optimization: Algorithms and Complexity
Christos H. Papadimitriou
Kenneth Steiglitz
http://store.doverpublications.com/0486402584.html