Materials

We are using the raw max flows (pdf) slides and the L17 Max flow slides.

Here is a complete set of L17 annotated slides and Tue’s version.

Topics

How to construct residual graphs

Bipartite Matching

Recall the construction. Given a bipartite graph, $G=(L,R,E)$ with the edges in $E$ going from nodes in $L$ to nodes in $R$, we construct a flow graph $G’$ as follows: add a source $s$ which connects to all nodes in $L$ and a sink $t$ with edges from each node in $R$ connecting to $t$. Set the edge capacities $c(e)=1$ for all edges in the graph, and we run FF or EK2.

Suppose there is a matching $M$ of size $k$ in $G$. Let $M={ (l_i, r_j)}$. It follows that $G’$ has a flow of value $k$ because we can send 1 unit of flow from $s \rightarrow l_i \rightarrow r_j \rightarrow t$ for each of the $k$ pairs in $M$. Since $M$ is a matching, that means that each $l_i$ and $r_j$ in this flow appears once, and thus all the capacity constraints and flow constraints are satisfied.

For the other direction, suppose that $G’$ has a flow $f$ such that $|f|=k$. By the integrality theorm we showed for FF and EK2, it follows that $f$ is integral, and thus, the flow on each edge is either $0$ or $1$ (because the capacity on each edge is set to 1). Define $M’$ to be the set of edges in the flow $f$ from a node in $L$ to a node in $R$ with $f(e)=1$. These edges are of the form $(l_i,r_j)$.

Since there is only 1 edge from $s$ to each node in $L$, this implies that in any valid flow, the inbound flow to a node in $L$ is at most one. By the flow constraint, that means that the outbound flow is at most 1. Since $f$ is a valid flow, we conclide that a node in $L$ appears at most once in $M’$. By a similar argument, a node in $R$ appears at most once in $M’$. Therefore $M’$ is a valid matching.

It remains to argue that $|M’|=k$. Consider the cut $S= {s} \cup L$. Recall that the value of the flow $f$ is equal to the value of flow leaving $S$ minus the value of flow entering $S$. In this case, there is no flow entering $S$ because none of the edges in $G’$ end with nodes in $L$. Therefore, the value of flow leaving $S$ must be $k$. Since each edge has capacity at most $1$, this means there must be flow leaving on $k$ edges that cross the cut $S$; thus $M’$ must contain $k$ edges.

Edge disjoing paths

Recall the transformation we discussed in lecture: Given an input graph $G=(V,E)$, we simply add edge capacities $c(e)=1$ for all $e\in E$.

Notice that if $G$ has $k$ edge-disjoint paths between nodes $s,t$, then $G$ has a flow of $k$. Simply set $f(e)=1$ for all edges along the $k$ disjoint paths from $s$ to $t$ and set the flow to 0 for all other edges.

The more difficult argument to make is that if $G,s,t$ has a flow of value $k$, then there exist $k$ edge-disjoint paths from $s$ to $t$. Intuitively, this follows, but we must actually identify the $k$ such paths, and this requires handling one special case of loops.

1. The first observation is the same as above; namely that if there is a flow of value $k$, then there is an integral flow of value $k$. In such a flow, each edge has either $f(e)=1$ or $f(e)=0$.

2. For an integral flow $f$, let $F_f$ be the set of edges $F_f={ e | f(e)=1}$ with flow of 1 in $G$ such that $|f|=k$. Then $F$ contains $k$ disjoint paths from $s$ to $t$.

We shall prove this by induction. If the flow value is 0, then the statement holds. Suppose the statement is true for flow value $i$, and now consider a flow value $i+1$. There must be an edge $(s,u)$ with $f(s,u)=1$. By the flow constraint, there must be an edge $(u,v)$ with $f(u,v)=1$, etc. Continue tracing such a path.

• If the path ends at $t$, then let we can output this path and reduce the flow along the edges of this path to 0. The resulting flow has value $i-1$, and our inductive hypothesis can be used to output $i-1$ edge disjoint paths, for a total of $i$.

• If the path ends at a node $v$ that we have already visited, i.e., if we identify a cycle of flow from node $v$ to node $v$, we can produce a new flow $f’$ with the same value by removing the flow along this cycle. The set $F_{f’}$ has a fewer number of edges, but the same flow value. We can repeat the procedure of tracing a flow path from $s$.

Node-disjoint paths

It is possible to find node disjoint paths by applying a clever transformation to the initial graph $G=(V,E)$ to produce a new graph. To construct this new graph $G’$, for every node $v\in V$, add a pair of nodes $v_{in}$, and $v_{out}$ to $V’$. Add the edge $(v_{in}, v_out)$ to the new graph, and additionally, for every inbound edge $(u,v)\in E$, add the edge $(u_{out}, v_in)$ to $E’$. For every outbound edge $(v,x)\in E$, add the edge $(v_{out}, x_{in})$ to $E’$. This defines the new graph $G’=(V’,E’)$. Now find edge-disjoint paths in $G’$. Notice that any path in $G$ that traverses node $v$ must traverse the edge $(v_{in},v_{out})$ in $G’$. This edge can only be used in one such path in $G’$. As a result, every edge-disjoint path in $G’$ corresponds to a node-disjoint path in $G$.