2
$\begingroup$

We're given a graph $G=(V, E)$, with source $s$ and sink $t$, $s\neq t$, and that all capacities are non-negative integers. Also the max flow itself is given, so we receive the value of max flow for each edge. We're also given some edge $e'$.

How can the max flow be found if we decrement the capacity value of an edge $e'$ by $1$ in linear time?

$\endgroup$
3
+50
$\begingroup$

If the capacity of edge $c(e') \ge f(e') + 1$ i.e. the max flow remains the same, there is no chance max flow increase, as it would increased without decreasing $c(e')$.

Suppose that $c(e') = f(e')$ (this edge is saturated) and we decrease the capacity in $1$ unit. You need to remove one unit of flow from $s$ to $t$ that goes through edge $e'$. Let say that $e'= (u,v)$.

Removing flow: Just run two BFS, one starting from $s$ to $u$ going through edges that has flow greater that $0$, the other from $v$ to $t$ equally from edges that has flow greater than $0$. (It is guaranteed you will reach your goal in both cases since there is a unit of flow traversing this edge). Select a path from $s$ to $u$ and remove $1$ unit of flow from each edge and do the same with a path from $v$ to $t$. Complexity: $O(|V| + |E|)$

Recover max flow: Now we have a valid flow network but not necessarily the network with max flow. So now you just need to run one iteration of augmenting path with the capacity of edge $e'$ reduced. (Just like running one iteration of Ford-Fulkerson algorithm) Running just one iteration has the complexity of a single DFS which is $O(|V| + |E|)$.

Overall complexity of this approach would be $(O|V| + |E|)$ which is linear in the amount of nodes and edges.

$\endgroup$
  • $\begingroup$ How do we know that only one iteration of Ford-Fulkerson will be enough? $\endgroup$ – Yos Jan 18 '18 at 17:45
  • 1
    $\begingroup$ Because flow will augment in at most one unit. $\endgroup$ – Marcelo Fornet Jan 18 '18 at 17:45
  • $\begingroup$ in the removing flow stage what if the edges adjacent to $u$ and/or $v$ have flow of exactly one? $\endgroup$ – Yos Jan 18 '18 at 17:48
  • $\begingroup$ What would be the problem in that case? the flow in all in the path from $s-u$ and $v-t$ get decreased by $1$ unit. If it was exactly $1$ the new flow is $0$. $\endgroup$ – Marcelo Fornet Jan 18 '18 at 20:39
  • $\begingroup$ @Yos I make a mistake, I didn't mean greater than 1, but greater than 0 (greater or equal than 1) $\endgroup$ – Marcelo Fornet Jan 18 '18 at 23:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.