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