Augmenting paths for Maxflow and Mincut

We discussed how to formulate the MAXFLOW problem for networks, i.e. arc-weighted digraphs {(V,D,c)} with two specific vertices, source {s} and sink {t} and arc capacities {c:D\rightarrow{\mathbb R}_+}, and treat it via linear programming. An alternative approach is via augmenting paths. The paths we talk about will disregard the arc directions in {D}, i.e. they will be {s}{t} paths in the underlying undirected graph. (When {e\in P} has the direction opposite to the arc in {D}, we write {e\in P\setminus D}.)

Definition 1 Given an {s}{t} flow {f:D\rightarrow {\mathbb R}_+}, an {f}augmenting path is an {s}{t} path {P} in the underlying graph, such that for each {e\in P}

  • if {e\in D} then {f(e)<c(e)};
  • if {e\not\in D} then {f(e)>0}.

The tolerance of {P} is

\displaystyle \tau(P):=\min(\min_{e\in P\setminus D} f(e), \min_{e\in P\cap D}c(e)-f(e)).

Note that the definition of tolerance extends unchanged to any path starting at {s}.

We can use {P} to improve {f}, as follows.

Lemma 2 For each {e\in D}, let

\displaystyle f'(e)=\begin{cases} f(e) & e\not\in P\\ f(e)-\tau(P) & e\in P\setminus D\\ f(e)+\tau(P) & e\in P\cap D \end{cases}.

Then {f'} is an {s}{t} flow in {(V,D,c)}, of value greater than that of {f} by {\tau(P).}

Proof: It is immediate from the definition of {\tau(P)} that {0\leq f'(e)\leq c(e)} for any {e\in D}. We still need to check the flow conservation constraints

\displaystyle \sum_{x: xv\in D} f'((xv))=\sum_{x: vx\in D} f'((vx))\quad\forall v\in V\setminus\{s,t\}.

If {P} visits {v\in V\setminus\{s,t\}} then there are two arcs, say, {xv} and {vy} on {v} that are affected when we change {f} to {f'}, and the changes in flow values cancel each other in each of the four cases (recall that {P} is a path in the underlying undirected graph). Finally, the value of {f'} is the net outflow from {s}, and the latter is greater than that of {f} by {\tau(P)}. \Box

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 {f} is maximum if and only if it does not have an {f}-augmenting path.

Augmenting paths are found by a breadth-first search from {s}. At some point, if we did not succeed in reaching {t}, we would end up with the set of vertices {S} reachable, in the underlying non-oriented graph, by paths with positive tolerance. Each {e\in D} crossing over from {S} to {T=V\setminus S} satisfies the property that {c(e)=f(e)}, and each arc {e} crossing from {T} to {S} satisfies {f(e)=0} — otherwise we would have added their vertices in {T} to {S}. Therefore,

\displaystyle {\mathrm val} (f)=\sum_{xy\in D: x\in S, y\in T} c((xy))=:{\mathrm cap} (S,T),

where on the right we have the definition of capacity of an arbitrary {s}{t} cut {(S,T)}.

It is easy to show that for an arbitrary {s}{t} cut {(S',T')}, one has {{\mathrm cap} (S',T')\geq {\mathrm val} (f)}. 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 {f}, and a corresponding to it minimum cut {(S,T)}.

Breadth-first search: Ford-Fulkerson algorithm

As usual in breadth-first search, we use a queue, i.e. a data structure {(Q,p,q)} that has two indices, one, {q}, pointing to the end of the queue, for new arrivals, and the other, {p}, pointing to the beginning of the queue, i.e. to the first element to be processed. There will be elementary operations:

  • {{\mathrm Insert} (Q,x)} – adds a new element, {x}, to the queue, and icrements {q}. In this case we also do not allow an element to enter the queue twice, so {{\mathrm Insert} (Q,x)} has no effect if {x} already was these once.
  • {x:={\mathrm First} (Q)} – takes the (currently) first element, {x}, from the queue, and icrements {p}—this will fail if {Q} is empty, i.e. if {p=q}.

Now the algorithm is as follows:

  1. Input: a feasible flow {f} in {(V,D,c)} with source {s} and sink {t}.
  2. Initialization: let {(Q,p,q)} be an empty queue; {{\mathrm Insert} (Q,s)}, and set {S:=\{(s,\infty)\}}.
  3. Loop: take {x:={\mathrm First} (Q)}. If this fails, return the first coordinates of the pairs in {S}—a minimum cut.
  4. for {v\in V} s.t. {(xv)\in D} and {f((xv))<c((xv))}, or s.t. {(vx)\in D} and {f((vx))>0}:
    • {{\mathrm Insert} (Q,v)}, {S:=S\cup\{(v,x)\}}.
    • if {v=t} then return the augmenting {s}{t} path by tracing back the pairs {(t,v_t)}, {(v_t,v_{t-1})},\dots, {(v_1,s)} in {S}.
  5. go to Loop.

So if {f} is not maximum we get an {f}-augmenting path, that can be used to improve {f}, and repeat. However, the speed of this procedure becomes unacceptable when the capacities are large. If {c\in\mathbb{Q}^{|D|}} then we are at least assured that it will converge after finitely many steps: indeed, we can multiply {c} by the least common multiple of its denominators, reducing to the case {c\in\mathbb{Z}^{|D|}}. Each iteration in this case improves the flow by at least {1}. 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 {2M}, when {M} is a large integer.

For irrational {c} the convergence not even need to be the case!

If one chooses a shortest {f}-augmenting path to improve {f} with, then the running time becomes bounded by {O(|V||D|^2)}—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.

Advertisements

Tags: ,

3 Responses to “Augmenting paths for Maxflow and Mincut”

  1. Yotam Medini Says:

    It would be nice to show an example with irrational capacities and an infinite sequence of augmenting paths.

  2. Yotam Medini Says:

    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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: