Maximum Flow

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!


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)


  • 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


  • 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

Last modified: Tuesday, 27 May 2014, 11:40 AM