# 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