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}$ .

Like this:

Be the first to like this post.

Tags: graph theory, MAS324

This entry was posted on 14 October, 2010 at 12:58 and is filed under undergrad maths. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

Equatorial Mathematics

Integer flows and graph theory applications

Like this:

Leave a Reply Cancel reply

Follow “Equatorial Mathematics”