## 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!

### 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