Applications of Network Flow

Edge Disjoint Paths Problem

Given:
- Directed or undirected graph $G$
- Vertices $s$ and $t$
- Parameter k

Task: Compute $k$ edge disjoint paths from $s$ to $t$

Directed Graph

Lemma: Number of edge disjoint paths equals max flow
- Construct a network flow $H$ where all edges have capacity $1$
- Since capacities are integral, the max-flow would have either $0$ or $1$ unit of flow on each edge
- Such a flow is called $0/1$ flow
- $|f_H| = \text{number of edge disjoint paths in G}$

Proof: Unclear

Algorithm:
- Start walking from $s$ along an edge with flow $1$
- If reach $t$, then add the path to the set of edge disjoint paths
- Else if reached a vertex a second time (a cycle!), then remove the edges that form the cycle
- Since $|f| \leq |V|$, Ford-Fulkerson outputs the flow in $O(|V||E|)$ time
- Extracting the paths from the flow takes $O(|E|)$ time
- Hence edge disjoint paths can be found in $O(|V||E|)$ time

Lemma: Maximum number of edge disjoint paths equals the minimum number of edges whose removal separates s from t
Proof:
$U \leftarrow$  set of edge disjoint paths
$F \leftarrow$ set of removed edges such that $s$ and $t$ are disconnected
First show $|U| \leq |F|$
- $F$ must contain at least one edge from each path in $U$
- Hence $|U| \leq |F|$

Now,
- $S = \{v \in V | \exists \text{ path from } s \text{ to } t \text{ which does not use any edge in } F \}$
- $T = V \setminus S$
- $F$ defines a cut $(S,T)$
- Clearly $|F| \geq c(S,T)$
- Any edge in $F$ that is not in the cut can be discarded to get $F_{minimal}$
- $|F_{minimal}| = c(S,T)$
- The smallest such set has size, $|F^*| =$ min-cut in $G$
- By Max-Flow Min-Cut theorem $|F^*| = |f_{max}|$, i.e max-flow in $G$
- By previous lemma $|F^*| =$ number of edge disjoint paths

Undirected Graph

- Double every edge to give 2 directed edges

- Repeat the algorithm for directed case

- Again $f$ might push flow along both $(u\rightarrow v)$ and $(v\rightarrow u)$ 

- But this is a cycle!

- Remove cycle and get on with life