## Integer flows and graph theory applications

Here we are continuing the story of Ford-Fulkerson algorithm. Assume that ${c:D\rightarrow {\mathbb Z}_+}$, i.e. the capacities are all integers. Then starting the Ford-Fulkerson from the zero flow, we see that at each iteration ${\tau(P)\in {\mathbb Z}_+}$. Thus the optimal flow will have integer values for each arc (such flows are called integral). We have

Corollary 3 A maxflow problem with integer capacities has an integral optimal solution.

This has various graph-theoretic applications. We can convert an undirected graph ${\Gamma=(V,E)}$ into a digraph by replacing each edge ${\{x,y\}}$ by a pair of opposite arcs ${xy}$ and ${yx}$, set all arc capacities to 1, and see what this implies for a pair of non-adjacent vertices ${s\neq t\in V}$. Running Ford-Fulkerson algorithm, we obtain an integral maximum ${s-t}$ flow ${f}$, of value ${k:={\mathrm val}(f)}$.

We also know that there is, by the maxflow-mincut Theorem, an ${s-t}$ cut ${(S,V\setminus S)}$ s.t. ${{\mathrm cap}(S,V\setminus S)={\mathrm val}(f)}$. Instead of capacity, it is more appropriate to talk here about the size ${|(S,V\setminus S)|}$ of the cut, i.e. the number of edges crossing from one part of the cut to another. Obviously, by definition of the capacity, we have ${{\mathrm cap}(S,V\setminus S)=|(S,V\setminus S)|}$.

The flow ${f}$ can be viewed as a collection ${D_f}$ of ${k}$ edge-disjoint ${\Gamma}$-paths from ${s}$ to ${t}$, as can be seen by induction on ${{\mathrm val}(f)}$: indeed, if ${{\mathrm val}(f)=1}$ then by construction (via the Ford-Fulkerson algorithm) ${D_f}$ is a path. Suppose now this statement holds for all ${k<{\mathrm val}(f)}$. As ${D_f}$ induces a connected subgraph, it contains a shortest path ${P}$. Then, ${P}$ is cut by a minimum cut ${(S,V\setminus S)}$—otherwise the cut does not cut! Removing all the edges of ${P}$ from ${D}$, we thus obtain a graph ${\Gamma'}$ that has the cut ${(S,V\setminus S)}$ of size ${{\mathrm val}(f)-\ell}$, for ${\ell>0}$. The flow ${f'}$ in ${\Gamma}$ corresponding to ${D_f\setminus P}$ has value ${{\mathrm val}(f)-\ell}$, and ${P}$ is an augmenting path for this flow, with ${\tau(P)=1}$. Thus ${\ell=1}$, i.e. ${(S,V\setminus S)}$ cuts just 1 edge in ${P}$, and by induction ${\Gamma'}$ contains ${k-1}$ edge-disjoint ${\Gamma}$-paths, and we obtain

Corollary 4 (Menger Theorem (for edge-disjoint paths)) The minimum size of an ${s-t}$ cut in ${\Gamma}$ equals the maximal number of edge-disjoint ${s-t}$ paths in ${\Gamma}$.

There is a graph transformation that allows one to prove Menger Theorem for internally disjoint ${s-t}$ paths (two paths between ${s}$ and ${t}$ are called internally disjoint is their only common vertices are ${s}$ and ${y}$). Our goal is to prove the following.

Theorem 5 (Menger Theorem (for internally disjoint paths)) The minimum size of an ${s-t}$ cut in ${\Gamma}$ equals the maximal number of internally disjoint ${s-t}$ paths in ${\Gamma}$.

Proof: Assume ${s}$ and ${t}$ are not adjacent. Replace each ${v\in V\setminus\{s,t\}}$ by a pair of vertices ${v_+}$, ${v_-}$, joined by an arc ${v_+ v_-}$. Then replace each edge ${\{x,y\}}$ of ${\Gamma}$ by a pair of opposite arcs ${xy}$ and ${yx}$. Replace every arc ${xy}$ such that ${s,t\not\in \{x,y\}}$ by the arc ${x_{-}y_{+}}$, each arc ${xy}$ with ${x=s}$ or ${x=t}$ by ${xy_+}$, and each arc ${xy}$ with ${y=s}$ or ${y=t}$ by ${x_-y}$. Now each ${s-t}$ path ${s,x^1,\dots,x^{k-1},t}$ corresponds to the path ${s,x^1_+,x^1_-,x^2_+,\dots,x^{k-1}_+,x^{k-1}_-,t}$ in the new graph, and the opposite holds, too: each ${s-t}$ path in the new graph has this form.

Assign capacities 1 to the arcs ${v_+ v_-}$, and infinite capacities (it suffices to take this “infinity” to be bigger than, say, ${10|E\Gamma|}$) to the rest of the arcs. Due to the choice of capacities, a minimum ${s-t}$ cut ${(S,V\setminus S)}$ will satisfy ${{\mathrm cap}(S,V\setminus S)\leq |E\Gamma|}$, and thus the only arcs from ${S}$ to ${V\setminus S}$ will be of type ${v_+v_-}$. Say, there will be ${k}$ such arcs. By (a straightforward generalisation of) Menger Theorem for edge-disjoint paths (to directed graphs), there will be exactly ${k}$ arc-disjoint ${s-t}$ paths in this digraph. By its construction, they cannot share a vertex ${v_-}$ (resp. ${v_+}$), as there is only one outgoing (resp. incoming) arc on it. Thus these paths are internally disjoint, and the corresponding ${k}$ paths in ${\Gamma}$ are internally disjoint, too. $\Box$

One more classical application is a maxflow-based algorithm to construct a maximum matching in a bipartite graph ${\Gamma=(V,E)}$, with the bipartition ${V=V_s\cup V_t}$. We add two more vertices ${s}$ and ${t}$ to it, and connect ${x\in\{s,t\}}$ to each ${v\in V_x}$ by an edge. In the resulting new graph ${\Gamma'}$ we solve the ${s-t}$ maxflow problem with all capacities set to 1. More precisely, we orient each edge so that each ${\{v_s,v_t\}}$, ${\{s,v_s\}}$, ${\{v_t,t\}}$ becomes an arc ${v_sv_t}$, respectively, ${sv_s}$, respectively ${v_tt}$.

Ford-Fulkerson algorithm, when started from the zero flow, will produce an integral maximal flow, of value ${k:={\mathrm val}(f)}$. As we know from Menger’s theorem, we will have ${k}$ internally disjoint ${s-t}$-paths. They will induce a matching ${M_f}$ on ${\Gamma}$ (just look at the ${\{v_s,v_t\}}$ edges only). On the other hand, any matching ${M}$ on ${\Gamma}$ can be used to construct an ${s-t}$-flow of value ${|M|}$ in ${\Gamma'}$ with all capacities 1. Hence ${M_f}$ is a maximum matching in ${\Gamma}$.

Advertisements

Tags: ,