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: ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: