Max-flow Part III

PDF of Eric’s handwritten notes are here.

Recall Max-flow problem

Given a flow network, find a flow of maximum size.

Recall Ford-Fulkerson algorithm

input: flow network with integer capacities c_e for e\in E.

  1. Set f_e=0 for all e\in E
  2. Build residual network G^f:
    • for \overrightarrow{vw}\in E:
      • if f_{vw}<c_{vw}: add \overrightarrow{vw} with residual capacity c_{vw}-f_{vw}
      • if f_{vw}>0: add \overrightarrow{wv} with residual capacity f_{vw}
  3. Check for a st-path P in G^f
    • If such path does not exist, return(f)
    • Otherwise, denote b= minimum residual capacity along P in G^f
  4. Augment f by b units along P
  5. Repeat from step 2 until no st-path can be found in G^f

Running time:

  • Let C= size of max-flow
  • The algorithm cost O(m) time per round
  • There will be at most C rounds (since the size of flow increases at least by 1 after every round)
  • Overall running time is O(mC).

We want the running time to be independent with capacities/size of flows.

Edmonds-Karp algorithm

This algorithm finishes in at most mn rounds and thus reaches overall running time O(m^2n). It also works with any positive capacities (remember that Ford-Fulkerson algorithm requires capacities to be integers).

Edmonds-Karp algorithm is identical to Ford-Fulkerson algorithm except Step 3:

3. Run BFS in G^f and take the path P with fewest edges.

And we are going to prove the following two claims:

  • a) in every round, at least one edge  is deleted from G^f
  • b) an edge is added or deleted from G^f at most n times

Since there are totally m edges, the number of rounds will be no more than mn.

For claim a), at least one edge e in P is fully occupied since b is the min residual capacity along P. And such e will be deleted afterwards.

For claim b), let’s see what happened when an edge is added to or deleted from G^f:

  • if \overrightarrow{vw}\in P is a forward edge then
    • \overrightarrow{vw} is deleted if it is fully occupied (i.e. f_{vw} = c_{vw})
    • \overrightarrow{wv} is added if previously f_{vw}=0
  • if \overrightarrow{zv}\in P is a backward edge then
    • \overrightarrow{zv} is deleted if flow on it is removed (i.e. f_{vz} = 0)
    • \overrightarrow{vz} is added if previously f_{vz}=c_{vz}

In G^f, let level(v)= minimum number of edges in paths from s to v. Note that G^f is changing so level(v) may also changes.

Claim: level(v) does not decrease during the execution of the algorithm

Proof: Note that in step 3 we take the shortest path P.

Let P=v_0\to v_1\to \dots \to v_l where v_0=s, v_l=t. We know that level(v_0)=level(s)=0.

Consider the relation between level(v_i) and level(v_{i+1}):

  • level(v_{i+1}) \leq level(v_i) + 1 by definition of level(\cdot)
  • level(v_{i+1}) \geq level(v_i) + 1 since otherwise there exist a shorter path s\to\dots\to v_{i+1}\to\dots\to t

Thus we know level(v_{i+1}) = level(v_i)+1 and level(v_i)=i in P.

For any v\in G, level(v) decreases iff some edge \overrightarrow{uv} is added where level(u) < level(v)-1 so s\to\dots\to u \to v makes v nearer to s. However, in order to add such \overrightarrow{uv} to G^f\overrightarrow{vu} must be in the shortest path P first. Thus we know level(u) = level(v)+1. \qquad\blacksquare

So level(v) must stay the same or increase during the execution of the algorithm.

Now consider what happens if an edge \overrightarrow{vw} is deleted from and later added into G^f:

  • When it is deleted we know level(w)=level(v)+1
  • When it is added later we know level(v)'=level(w)'+1

Since level(\cdot) never decrease we know level(v)'=level(w)'+1\geq level(w)+1=level(v)+2. Which means if an edge \overrightarrow{vw} is deleted and added later then level(v) at least increases by 2.

Thus an edge can be deleted and added later for no more than n/2 times since level(\cdot)\leq n.

And remember that at least 1 edge is deleted each round we know the total number of rounds is no more than nm.

Thus the overall running time of Edmonds-Karp algorithm is O(nm^2).

Best algorithm for max-flow problem in current runs in O(nm) time by [Orlin ’13].

Advertisements