Maximum Flows In Network Graphs

Bart Massey

Flow Graphs

• Directed graph G, with two distinct vertices s and t.

  • Vertex s is the "source" of flow in the graph, while t is the "sink".
  • Every vertex v in G must be along some path s..v..t
  • Consequence: |E| >= |V| - 1
  • Additional restriction: if (u,v) is in E, (v,u) may not be.

• Edges of G labeled with capacity c : E -> N

  • N WLOG

• Edges of G also labeled with flow f : E -> N

  • for all (u,v) in G, f(u,v) <= c(u,v)

• Flow f(G) of graph is sum(s,v) in E

Max Flow

• For a given graph G and capacity labeling c, find a flow f maximizing f(G)

• Obvious questions:

  • Is there an algorithm to find f? [yes]
  • Is there a polytime algorithm to find f? [yes]
  • How efficient can the algorithm be? [|V|^3 -ish]

Residual Graph and Augmenting Flow

• Given flow graph G construct residual flow graph G':

  • Vertices of G' are vertices of G
  • Edges of G' are edges (u,v) of G such that c(u,v) > f(u,v) together with back-edges for every edge of G
  • Capacity c' of an edge (u,v) in G' is c(u,v) - f(u,v)
  • Capacity of a back-edge (u,v) in G' is f(u,v)

• Augmenting flow in G is a path p with positive flow in G'

  • Because of the way G' is constructed, if p exists, then adding its flow to G will (legally) increase the flow of G
  • Further [hard proof], if no p exists, then G has max flow!

Ford-Fulkerson

initialize f to 0 for all edges in G
while there is an augmenting path p in G'
    augment f along p
return f

• Obvious way to find p is depth-first search

  • Leads to worst-case running time O(fmax)

• Breadth-first search for p gives Edmonds-Karp

  • Worst-case O(|V||E|^2)

Min-Cut

• A cut on a flow graph is a set of edges that partition V into two connected sets: one including s and one including t

• Any edges from s side are positive; any from t side are negative

• The flow across a cut C is the (proper-signed) sum of the flows in the edges of C

• If f is maximal on G, then there exists a cut C on G such that f(C) = f(G)

• Intuitively, this cut is the "bottleneck" for the flow

Push-Relabel

• Excess: function e : V -> N which, when positive, indicates "excess" flow entering a vertex

• Relabel: Establish a new partial ordering on V, represented by a height function h : V -> N

  • Intuitively, higher vertices are nearer the source
  • Increase h(V) by 1

• Push: Move excess flow "downhill" from a vertex u to a neighbor v with h(u) = h(v) + 1

Push-Relabel Algorithm

-- init
set f, h, e to 0
h(s) <- |V|
for each v in neighbors of s
    f(v) <- c(s,v)
    e(v) <- c(s,v)
    e(s) <- e(s) - c(s,v)
-- run
while there exists a legal relabel or push
    do it
return f

Relabel-To-Front Algorithm

• Particular, efficient (V^3) case of push-relabel

• Works by "discharging" vertices (getting rid of all their) flow in a particular fixed order

• Details are in the book

Application: Bipartite Matching

• Note that one can do multi-source S + multi-sink T by adding a new source s' and sink t' with s' connected to S and T' connected to T: set capacities maximally (infinity??)

• Max Bipartite Matching Problem: Given a bipartite graph G, find a set of edges E' such that no vertex v is part of two edges of E', maximizing |E'|

• Set up multi-network-flow problem, find set of edges maximizing flow