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

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.)