\begin{center} Lecture 9: Advanced Max Flow Algorithm \end{center}

Different Variants of the Max Flow Problem

So far, we were focused on the “canonical” maximum flow problem formulation. In some of the applications though, one needs to solve different variants of this problem. Amazing thing about the maximum flow problem is that many of these, seemingly, more general variants can be reduced to the “canonical” problem.

Some examples:

• (Multiple source-sinks maximum flow) We have multiple sources $s_1, \ldots, s_k$ and multiple sinks $t_1, \ldots, t_{k'}$ and just want to push as much flow as possible between them.
  • Reduces to canonical maximum flow by adding a “super-source” $s$ and “super-sink” $t$ and arcs with unbounded (or just $nU$) capacity from $s$ to each $s_i$ and from each $t_i$ to $t$.
  • Computing maximum flow in the new graph corresponds directly to solving the multiple source-sink version.
• (Multiple source-sinks maximum flow with demands) Again, we have multiple sources and sinks, but now we want each source $s_i$ to supply a prescribe amount $d_i^+$ of flow and each sink $t_j$ to demand a prescribed amount $d_j^-$ of flow. (Assuming that $\sum_i d_i^+ = \sum_j d_j^-$.)
  • Do the same reduction as before but make the capacity of the edge connecting $s$ to $s_i$ be $d_i^+$ and the capacity of the edge connecting $t_j$ to $t$ be $d_j^-$.
  • Send flow $f'$ along the lower bounds.
  • This makes them be satisfied but creates new residual arcs and demands.
  • Solve the resulting multiple source-sink with demands in the residual graph, obtaining a solution $\hat{f}$.
  • The final solution is the flow $f:=f'+\hat{f}$. Note: that we are using linearity of the flows here. That is, that adding a feasible flow $f'$ in a graph to a flow that is feasible in the residual graph of $f'$ gives us a feasible flow in the original graph.
• (Bipartite matching problem) Let $G=(V,E)$ be an undirected graph that is bipartite, i.e., $V=S\cup T$, such that $S\cap T=\emptyset$ and $E\subseteq S\times T$. We want to find a maximum cardinality matching $M$ in $G$. That is, a subset $M$ of edges such that no two edges in it share an endpoint.
  • Setup a graph $G'$ which is a copy of $G$ such that: we make each original edge have capacity $1$ and be oriented towards the vertex in $T$ (important!), and then we add a super-source $s$ (resp. super-sink $t$) that is connected via directed unit-capacity edges to each vertex in $S$ (resp. there is a directed unit-capacity edge from each vertex in $T$ to $t$).
  • One can show that in the maximum integral $s$-$t$ flow in this graph (which we know always exists) all the original edges that flow non-zero amount of flow form a maximum matching.
  • The above shows us that one can reduce bipartite matching problem to the maximum flow problem. Can one go the other way too? Yes! (But we will not cover that.)
• (Vertex capacities) Find a maximum $s$-$t$ flow in a graph where we do not have any edge capacities but we cap the total flow flowing through each vertex $v$ at $u_v$.
  • Transform the graph by splitting every vertex $v$ into two vertices $v_{in}$ and $v_{out}$, connecting all the original incoming edges to $v_{in}$ and all the original outgoing edges to $v_{out}$, and then adding an edge $(v_{in}, v_{out})$ with capacity $u_v$.
  • Finding an maximum $s$-$t$ flow in this new graph (with respect to edge capacities) gives us the maximum $s$-$t$ flow in the original graph that is feasible with respect to vertex capacities.

Strongly Polynomial Max Flow Algorithm

• So far, our crowning achievement was an $O(m^2 \log U)$ maximum flow algorithm that we got via scaling. Still, even though this running time is polynomial in the size of our graph and the representation of its capacities, i.e., weakly polynomial, one could aim for strongly polynomial running time. That is, a running time that does not depend at all on $U$, just on the number of vertices and edges of the graph. (We assume here that elementary arithmetic operations on numbers can be performed in $O(1)$ time.)
• How to get such an algorithm?
• Recall: Our algorithms so far were “primal” greedy. That is, they applied a greedy strategy in which we improve our current solution in each step and then lower bounded the progress made by each such step in terms of the value of the max flow.
• Intuition: As the value of the max flow directly depends on the value of our capacities, this kind of “primal” greedy approach is inherently incapable of delivering strongly polynomial bounds.

  $\Rightarrow$ We need a different way to measure our progress towards optimality.

• Recall: The way we certified the optimality of our current flow $f$ was by looking whether $s$ and $t$ are connected in $G_f$. If not, $f$ was already a max flow; otherwise, it was not optimal (and the $s$-$t$ path enables us to improve it).
• Can we make this yes/no statement quantitative to also be able to differentiate between the flows that are “almost maximum” and the ones that might be “far” from being maximum?

• Idea: Let us consider the $s$-$t$ distance $d_f(s,t)$ in the residual graph $G_f$. (We assume here that each edge with positive residual capacity has length of one, and every edge with zero residual capacity has length $+\infty$.)
• Note: Any feasible flow in $G_f$ has to have a fixed total volume (at most $m$, if all capacities are $1$).

  $\Rightarrow$ If $s$ and $t$ far apart, not much flow can “fit” in network, as each flow path has to “utilize” a lot of volume. (Think: an $s$-$t$ path graph vs. a graph consisting of multiple parallel $(s,t)$ edges.)

• Key observation: If $d_f(s,t)\geq n$, $s$ and $t$ are disconnected in $G_f$.

  $\Rightarrow$ $f$ is already a maximum flow.

Our New Goal: Design an augmenting path based algorithm that aims to increase the $s$-$t$ distance $d_f(s,t)$ in the residual graph. (Instead of trying to directly push as much flow "as possible” in each iteration - which was the case before in the maximum bottleneck capacity augmenting path algorithm.)

• What are the best augmenting paths to use if we are interested in increasing $d_f(s,t)$?
• Intuition: Shortest (augmenting) paths are the "obstacles" to $d_f(s,t)$ being large. So, let's try to "destroy" them.

  $\Rightarrow$ How to "destroy" an augmenting path in $G_f$? Augment the flow using it!

• Note: Finding the shortest augmenting path correspond to running BFS in the residual graph. So, it take $O(m)$ time. (The same as the "normal" augmenting path search.)
• Challenge: How to ensure that this augmentation does not introduce new shortest paths in $G_f$? In principle, this might even reduce $d_f(s,t)$ instead of increasing it.
• Fortunately, this cannot be the case. But we need to prove that!
• Lemma: For any vertex $v$, if $d(v)$ (resp. $d'(v)$ is the distance from $s$ to $t$ in the residual graph before (resp. after) augmenting the flow along some shortest augmenting path, then $d(v)\leq d'(v)$.
• So, the distance from $s$ does not decrease not only for $t$ but for every vertex. (Note that the proof relies on establishing this stronger claim - it is one of the examples when sometime proving a stronger claim is actually easier.)
• By symmetry, one can argue that the distance from any vertex $v$ to $t$ is non-decreasing as well.
• Proof:
  • Assume for the sake of contradiction that this is not the case.
  • Let $A$ be the (non-empty) set of vertices $u$ for which $d(u)>d'(u)$. Take $v$ to be the vertex with minimal $d'(v)$ among all vertices in $A$.
  • Let $P'$ be the shortest $s$-$v$ path in the residual graph after augmentation, and let $w$ be the vertex preceding $v$ on this path. (Note that we cannot have that $v=s$, so such path and $w$ exist.)
  • Note $d'(v)=d'(w)+1$. Moreover, we must have that $d(w)\leq d'(w)$ as otherwise $w\in A$ and $d'(w)< d'(v)$, which would contradict minimality of $v$.
  • We claim that the last edge of $P'$, i.e., $(w,v)$, had zero residual capacity before augmentation by $P$. Otherwise, we would have that \[ d(v)\leq d(w)+1 \leq d'(w)+1 = d'(v), \] and thus contradict the fact that $v\in A$.
  • The only way for the edge $(w,v)$ to have non-zero residual capacity after augmentation by $P$ would be if the edge $(v,w)$ belonged to $P$.
  • But $P$ was the shortest path before the augmentation.

    $\Rightarrow$ $d(w)=d(v)+1$.

  • However, all of that means that \[ d(v)=d(w)-1\leq d'(w)-1=d'(v)-2\leq d'(v), \] which contradicts our assumption that $v\in A$.

• So, augmenting the flow using shortest paths indeed does not make things worse. But does it make them better?
• Yes! But, again, we need to prove that.
• Lemma: We have at most $\frac{mn}{2}$ shortest path flow augmentations before $d_f(s,t)\geq n$ (and thus $f$ is the maximum flow).
• Proof:
  • Each flow augmentation saturates at least one "bottlenecking" edge $(u,v)$.
  • Before this edge is used saturated again in some subsequent flow augmentation, we must have pushed some flow via an augmenting path that contained the opposite edge $(v,u)$.
  • Let $d(w)$ be the distance of $s$ to $w$ in the residual graph just before the first saturation of $(u,v)$, and let $d'(w)$ be the corresponding distance just before the flow was pushed along $(v,u)$.
  • As we always use shortest paths to augmenting flow we need to have that $d(v)=d(u)+1$ and $d'(u)=d'(v)+1$.
  • But, by the lemma we proved above, we know that $d(v)\leq d'(v)$.

    $\Rightarrow$ We thus need to have that \[ d'(u)=d'(v)+1\geq d(v)+1 = d(u)+2. \]

    $\Rightarrow$ The distance from $s$ to $u$ had to increased by at least $2$ by the time the edge $(u,v)$ can again be saturated by some augmenting path.

    $\Rightarrow$ $(u,v)$ can be saturated at most $\frac{n}{2}$ times before the $s$-$u$ distance becomes $\geq n$ and thus $d_f(s,t)\geq n$ as well.

  • Each edge can be saturated at most $\frac{n}{2}$ times. So, there is at most $\frac{mn}{2}$ saturations and thus flow augmentations.
• Total running time: $O(m^2 n)$. Strongly polynomial!
• Note: In this analysis we have no way of lower bounding how much flow a particular flow augmentation pushed. We just can argue that over all the $\frac{mn}{2}$ augmentations we managed to push the whole max flow value (no matter how large it was!). This is an important feature of so-called primal-dual algorithms. (Will get back to this later on.)