Max-flow algorithms

Ford-Fulkerson: PDF of Eric’s handwritten notes are here.
Edmonds-Karp: PDF of Eric’s handwritten notes are here.

Max-flow problem

Sending supply (e.g., internet traffic, products) from vertex s to vertex t without exceeding edge capacities.

Flow network

Directed graph G=(V,E) with designated source s\in V and sink t\in V; a capacity c_e>0 for each e\in E.

f_e is the flow along the edge e. We want to maximize the flow from s to t.

Constraints:

  1. Capacity constraint: for all e\in E, 0\le f_e\le c_e
  2. Conservation of flow: for all v\in V\backslash\{s\cup t\}, flow-in v = flow-out v, in other words:
           \sum_{\overrightarrow{wv}\in E}f_{wv}=\sum_{\overrightarrow{vz}\in E}f_{vz}

\text{size}(f) = total flow sent = flow-out s = \sum_{\overrightarrow{sv}\in E}f_{sv} = flow-in t = \sum_{\overrightarrow{zt}\in E}f_{zt}.

Simple algorithm idea

(see handwritten notes for an example)

  • start with f_e=0 for all e\in E
  • find an s-t path p with available capacity
  • increase the flow along p until some edge hits its capacity
  • repeat until no such s-t path exists

This approach doesn’t work, since sometimes need to decrease flow along some edges to increase the total flow (see the handwritten notes for such an example).

Residual network

For a flow network on G=(V,E) with capacities c_e and flow f_e, residual network G^f=(V,E^f) has edges:

  • if \overrightarrow{vw}\in E and f_{vw}<c_{vw}, then add \overrightarrow{vw} to G^f with capacity c_{vw}-f_{vw}
  • if \overrightarrow{vw}\in E and f_{vw}>0, then add \overrightarrow{wv} to G^f with capacity f_{vw}

Ford-Fulkerson algorithm

  1. set f_e=0 for all e\in E
  2. build the residual network G^f for the current for f
  3. check for a s-t path P in G^f, if there is no such path, return f as the output
  4. let c(P) be the minimum capacity along P in G^f
  5. augment f along P by c(p):
    • for a forward edge e\in P, increases f_e by c(P)
    • for a backward edge \overrightarrow{vw}\in P, decrease f_{wv} by c(P)
  6. repeat from step 2.

Runtime

If capacities are integers, then the flow increases by \ge 1 unit each iteration. So if C = size of max-flow, it requires \le C iterations.

Each iteration involves a DFS or BFS, so takes O(|V|+|E|)=O(|E|) time (assuming G is connected). Therefore the overall runtime is O(|E|C). This is pseudo-polynomial since it depends on the numbers in the input.  We want the running time to be independent of the capacities and the size of the flow.

Better algorithm: [Edmonds-Karp ’72] takes the shortest augmenting path in G^f, which results in O(|V||E|) rounds, O(|V||E|^2) total time.


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.

To analyze the running time of the Edmonds-Karp algorithm, 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

Hence, since there are 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).

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

 

Advertisements