[Math] Find the maximum number of edge-disjoint paths

algorithmsgraph theorynetwork-flow

Supposing I have an undirected graph G = (V, E); which polynomial-time algorithm can I use, for two vertices s and t, to find a maximum value for k, such that there will be k pairwise edge-disjoint paths from s to t?

Best Answer

Split each undirected edge $\{v,u\}$ of the graph $G$ into a couple of two oppositely directed directed edges $(v,u)$ and $(u,v)$ of capacity $1$ (or by a cycle $v-[vu]-u-[uv]-v$ with two added dumb vertices $[vu]$ and $[uv]$, if you have doubts dealing with directed graphs with coples of two oppositely directed directed edges). It is easy to check that both the initial graph $G$ and the splitted graph $Gā€™$ has the same values for a maximum $s$-$t$ flow, maximum number of pairwise edge-disjoint paths from $s$ to $t$, and a smallest $s$-$t$ cut. You can read more about proofs of the equalities of all these values and algorithms for their calculation in Lectures 2-4 from our block course "Algorithmic Graph Theoryā€.