26-4 Updating maximum flow

Let $G = (V, E)$ be a flow network with source $s$, sink $t$, and integer capacities. Suppose that we are given a maximum flow in $G$.

a. Suppose that we increase the capacity of a single edge $(u, v) \in E$ by $1$. Give an $O(V + E)$-time algorithm to update the maximum flow.

b. Suppose that we decrease the capacity of a single edge $(u, v) \in E$ by $1$. Give an $O(V + E)$-time algorithm to update the maximum flow.

a. Just execute one iteration of the Ford-Fulkerson algorithm. The edge $(u, v)$ in $E$ with increased capacity ensures that the edge $(u, v)$ is in the residual network. So look for an augmenting path and update the flow if a path is found.

Time

$O(V + E) = O(E)$ if we find the augmenting path with either depth-first or breadth-first search.

To see that only one iteration is needed, consider separately the cases in which $(u, v)$ is or is not an edge that crosses a minimum cut. If $(u, v)$ does not cross a minimum cut, then increasing its capacity does not change the capacity of any minimum cut, and hence the value of the maximum flow does not change. If $(u, v)$ does cross a minimum cut, then increasing its capacity by $1$ increases the capacity of that minimum cut by $1$, and hence possibly the value of the maximum flow by $1$. In this case, there is either no augmenting path (in which case there was some other minimum cut that $(u, v)$ does not cross), or the augmenting path increases flow by $1$. No matter what, one iteration of Ford-Fulkerson suffices.

b. Let $f$ be the maximum flow before reducing $c(u, v)$.

  • If $f(u, v) = 0$, we don't need to do anything.
  • If $f(u, v) > 0$, we will need to update the maximum flow. Assume from now on that $f(u, v) > 0$, which in turn implies that $f(u, v) \ge 1$.

Define $f'(x, y) = f(x, y)$ for all $x, y \in V$, except that $f'(u, v) = f(u, v) - 1$. Although $f'$ obeys all capacity contraints, even after $c(u, v)$ has been reduced, it is not a legal flow, as it violates flow conservation at $u$ (unless $u = s$) and $v$ (unless $v = t$). $f'$ has one more unit of flow entering $u$ than leaving $u$, and it has one more unit of flow leaving $v$ than entering $v$.

The idea is to try to reroute this unit of flow so that it goes out of $u$ and into $v$ via some other path. If that is not possible, we must reduce the flow from $s$ to $u$ and from $v$ to $t$ by one unit.

Look for an augmenting path from $u$ to $v$ (note: not from $s$ to $t$).

  • If there is such a path, augment the flow along that path.
  • If there is no such path, reduce the flow from $s$ to $u$ by augmenting the flow from $u$ to $s$. That is, find an augmenting path $u \leadsto s$ and augment the flow along that path. (There definitely is such a path, because there is flow from $s$ to $u$.) Similarly, reduce the flow from $v$ to $t$ by finding an augmenting path $t \leadsto v$ and augmenting the flow along that path.

Time

$O(V + E) = O(E)$ if we find the paths with either $\text{DFS}$ or $\text{BFS}$.