Graph problem regarding Max-Flow Min-Cut while modifying capacity of an edge

Question

Ok so i have the following problem, which is based on the Max Flow Min Cut Theorem:

Let $R = (G, s, t, c)$ be a transportation network, where $c : E(G) → Z^{∗}_{ +}$. Consider $e = uv ∈ E$ and $p ∈ Z$. Let $R^{p}$ be the network obtained from $R$ by adding $p$ to the capacity of $e$ (basically $R^{0} = R$) and denote by $v(R^{p})$ the maximum value of a flow in $R^{p}$.

(a) Prove that $v(R^{-1}) ⩾ v(R)−1$ and equality holds if and only if $e$ belongs to at least one minimum capacity cut in $R$.

So i understand how $v(R^{-1}) = v(R)−1$ could work, because if we decrease the capacity of an edge from a min cut then the total capacity of the cut also decreases by one. But what i don't understand is how it could be bigger if we decrease instead of increase the capacity.

(b) Devise an efficient algorithm for finding a flow of maximum value in the network $R^{p}$ when $−c(e) ⩽ p < 0$, having a maximum flow in $R$.

It is not specified anymore that $e$ belongs in a min cut. I suppose we could check if there are any augmented paths that include $e$.

Answer 1

For (a), note that if there are multiple max flows, then it is possible for $v(R^{-1}) = v(R)$. It's never true that $v(R^{-1}) > v(R)$, but there can be equality! Here's such an example graph where decreasing the capacity of edge $uv$ does not change the maximum flow:

For (b) there are two steps. The first is taking the flow $f$ for $R$ and making a valid (not necessarily maximum) flow $f'$ for $R^{p}$. The second is making this new flow a maximum flow for $R^{p}$.

Creating a valid flow

When we decrease $e=uv$'s capacity by $1$, a flow can be invalidated if $f(e) = c(e)$ before the decrease. Therefore, we must set $f'(e) = f(e) - 1$. This can invalidate the in=out rule for all vertices. So, consider constructing shortest (unweighted) paths from $s$ to $u$ and $v$ to $t$ in $G_f$. Convince yourself that decreasing the flow by $1$ along each edge of these paths makes the flow $f'$ valid again, and this takes time $O(|V| + |E|)$. Repeating this $p$ times takes a total of $O(p\cdot (|V| + |E|))$.

Creating a maximum flow

Consider how the general Ford Fulkerson framework finds a max flow:

1. Initialize $f$ to be an empty flow and $G_f$ the residual graph associated with $f$.
2. While $f$ is not a maximum flow:
   1. Find an augmenting path $p$ from $s$ to $t$ in $G_f$ using BFS/DFS.
   2. Update $f$ (and $G_f$) to add one unit of flow along each edge in $p$.
3. Return the resulting flow.

Thus, the Ford Fulkerson algorithm runs in time $O(v(R) \cdot (|V| + |E|)$. Furthermore, given an intermediate flow $f'$ as a starting point, Ford Fulkerson makes at most $v(R) - |f'|$ BFS/DFS calls. In your case, $v(R^{-p}) \ge v(R) - p$, so this step takes time $O(p \cdot (|V| + |E|))$.

Therefore, the overall runtime is $O(p\cdot (|V| + |E|))$.