Next, we'll consider a problem kind of similar to ones we've seen before, dealing with paths between two vertices $s$ and $t$. Here, we want to know how many different paths there are from $s$ to $t$ which don't share any edges.
Definition 16.1. Let $G = (V,E)$ be a graph. Two paths on $G$ are said to be edge-disjoint if they do not share an edge.
Example 16.2. Consider the following graph. The two highlighted paths both travel to and from the same vertices and even touch some of the same vertices along the way, but they do not share any edges.
Naturally, we want to find all such paths.
Problem 16.3. The edge-disjoint paths problem is: Given a graph $G = (V,E)$ and two vertices $s,t \in V$, find the maximum number of edge-disjoint paths from $s$ to $t$.
So why would we want to know how many edge-disjoint paths there are in a graph? Intuitively, this has to do with a similar notion that we considered when thinking about maximum flows. If you're a typical driver and you encounter some slowdown on a route to your destination, you have a few options. One option is to sit in traffic and wallow in anger
The other option is that you snap, turn around, and try another route. This was the idea behind our residual graph, the fact that there can be a redistribution to some other part of the network. However, the second option only works if there's another route for you to get to. What if all of your routes happen to share an edge that's blocked? Then it's back to being mad.
This also suggests something about the structure of the graph. Removing this edge would remove the ability to get from one part of the graph to the other. In other words, it seems like our discussion about cuts and connectivity have something to do with these disjoint paths.
First, we can attempt to transform this into a maximum flow problem again.
Proposition 16.4. A directed graph $G$ has $k$ edge-disjoint paths from $s$ to $t$ if and only if the flow network $G'$ has an integral flow of value $k$.
Proof. Let $G = (V,E)$ be a digraph and choose $s$ and $t$. Then we define the flow network $G' = (V,E,s,t,c)$, where $c(e) = 1$ for all edges $e \in E$.
We first consider the forward direction. Let $P_1, \dots, P_k$ be edge-disjoint $s,t$ paths on $G$. We define the flow $f$ as follows: \[f(e) = \begin{cases} 1 & \text{if $e$ is in a path $P_i$, $1 \leq i \leq k$,} \\ 0 & \text{otherwise.} \end{cases}\] One can easily verify that this is a flow with $v(f) = k$.
Now, consider a flow $f$ on $G'$ with value $k$. We will show that there are $k$ edge-disjoint paths by induction on the number of edges $\ell$ in $f$ that have flow. If $\ell = 0$, then $v(f) = 0$ and we're done.
Now consider $\ell \geq 1$ and assume for flows $f'$ with $\ell' \lt \ell$ edges carrying flow that there are $v(f')$ edge-disjoint paths in $G$. Then there exists an edge $(s,u)$ that has $f(s,u) = 1$. Since our flow must satisfy conservation, we can follow the flow of that edge. There are two cases: either we follow the flow to $t$ or we follow the flow back to $u$.
If we follow the flow to $t$, we consider the path $P$ traced by this flow to be one of our $s,t$ paths. Now let $f'$ be the flow with $f(e) = 0$ for $e \in P$. Then $v(f') = k-1$ and there are fewer edges carrying flow in $f'$. By our inductive hypothesis, there are $k-1$ edge-disjoint paths. Then $P$ is our $k$th edge-disjoint path in $G$.
If we follow the flow back to $u$, then our flow has a cycle $C$. This time, we modify our flow $f$ into a flow $f'$ to remove any flow on edges of $C$.
Then $v(f') = k$ and $f'$ has flow being carried on fewer edges, so by our inductive hypothesis, there are $k$ edge-disjoint paths in $G$. $$\tag*{$\Box$}$$
Again, we can ask about the running time of this transformation. Here, we use $C = k$ again, since our flow will be constrained by the number of edge-disjoint $s,t$ paths, which is constrained by the number of outgoing edges of $s$. In the worst case, we have $k = |V| = n$, giving us $O(mn)$ time by using the classical Ford-Fulkerson algorithm.
Now, we can revisit our discussion about connectivity in graphs. First, we have the following definition.
Definition 16.5. An edge cut is a set of edges $F \subseteq E$ such that $H = (V,E-F)$ is disconnected. We say that $F$ separates two vertices $u$ and $v$ if there is no path from $u$ to $v$ in $H$.
Example 16.6. Consider the following directed graph, with the edge-disjoint paths highlighted. The edges with a red line through them represent an edge cut corresponding to the vertex cut $(S,T)$, where $S$ consists of vertices highlighted in orange and $T$ consists of vertices highlighted in blue.
Although we didn't see this before, we begin to see why these notions are cuts: if we cut these things out of our graphs or we do cuts in between them, we effectively disconnect the graph. The following theorem about paths and cuts is due to Menger in 1927 and is called Menger's Theorem.
Theorem 16.7 (Menger). Let $G = (V,E)$ be a directed graph and let $s,t \in V$ be vertices. The maximum number of edge-disjoint $s,t$ paths is equal to the size of an edge cut that separates $s$ from $t$.
Proof. First, suppose $F$ is an edge cut that separates $s$ from $t$. Then every $s,t$ path must contain at least one edge in $F$. Then the number of edge-disjoint $s,t$ paths is at most $|F|$.
Now, suppose there are at most $k$ edge-disjoint $s,t$ paths. By Proposition 16.4, there is a maximum flow $f$ of value $k$ in the network $G'$. Then by the Max-Flow Min-Cut Theorem, there exists a cut $(S,T)$ of capacity $k$. Let $F$ be the cutset of the cut $(S,T)$. Then $F$ is an edge cut that separates $s$ and $t$. Since every edge has capacity 1, we must have $|F| = k$. $$\tag*{$\Box$}$$
In a spooky coincidence, the edge cut based on our edge-disjoint paths corresponds to the cutset of the minimum cut of the graph! This turns out to be a more specific version of the max-flow min-cut theorem (or you can think of the max-flow min-cut theorem as a generalization of Menger's theorem).
Now, we can go even further and consider the same question on undirected graphs. The standard trick to turning an undirected graph into a directed graph is to turn each edge of the undirected graph into two antiparallel directed edges. This gets us most of the way there.
Example 16.8. Consider the following directed graph formed by making turning every edge of an undirected graph into two antiparallel edges. The two highlighted paths are edge-disjoint in the directed graph, but would not be edge-disjoint in the undirected graph.
Luckily, this is not too hard to deal with.
Lemma 16.9. Let $G'$ be a flow network. Then there is a maximum flow $f$ such that for all antiparallel edges $(u,v)$ and $(v,u)$, either $f(u,v) = 0$ or $f(v,u) = 0$.
Proof. Let $f$ be a maximum flow. We will define a flow $f'$ in the following way. Let $(u,v)$ and $(v,u)$ be antiparallel edges with $f(u,v), f(v,u) \gt 0$. Let $\delta = \min\{f(u,v), f(v,u)\}$. Then $f'(u,v) = f(u,v) - \delta$ and $f'(v,u) = f(v,u) - \delta$. $$\tag*{$\Box$}$$
Then the following clearly holds.
Theorem 16.10. A undirected graph $G$ has $k$ edge-disjoint paths from $s$ to $t$ if and only if the flow network $G'$ has an integral flow of value at least $k$. Furthermore, the maximum set of edge-disjoint paths can be computed in $O(mn)$ time.
We also get the following undirected version of Menger's theorem.
Theorem 16.11 (Menger). Let $G = (V,E)$ be an undirected graph and let $s,t \in V$ be vertices. The maximum number of edge-disjoint $s,t$ paths is equal to the size of an edge cut that separates $s$ from $t$.
There are also versions of Menger's theorem concerning vertex-disjoint paths, which talk about the number of vertices that need to be removed to disconnect a graph.
While we proved Menger's theorem using flows, it's obvious that Menger did not prove his theorem that way, since it predates the max-flow min-cut theorem by almost thirty years. Interestingly enough, Menger moved to Chicago following the Second World War and he was a faculty member at IIT.