9
$\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$
1

1 Answer 1

13
+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$
10
  • $\begingroup$ How do we know that only one iteration of Ford-Fulkerson will be enough? $\endgroup$
    – Yos
    Commented Jan 18, 2018 at 17:45
  • 2
    $\begingroup$ Because flow will augment in at most one unit. $\endgroup$ Commented Jan 18, 2018 at 17:45
  • 1
    $\begingroup$ @Addem actually this solution is $O(|E|)$ since you are only traversing the graph using dfs/bfs three times starting from a fixed node (you don't need to iterate over the nodes). $\endgroup$ Commented Apr 10, 2020 at 0:37
  • 1
    $\begingroup$ @Addem I'd also add that one often assumes a network graph is connected so $|E| \geq |V| -1 $ thus $𝑂(|𝑉| + |𝐸|)$ = $𝑂(|𝐸|)$. $\endgroup$ Commented Apr 10, 2020 at 2:07
  • 1
    $\begingroup$ Check the following graph A -> B (cap: 1) B -> C (cap: 1) C -> D (cap: 1) B -> D (cap: 1) Max flow initially is (1), solution is not unique. If you select A -> B -> C -> D in your solution, and then C -> D capacity is decreased (from 1 to 0). Then a new max flow will appear: A -> B -> D. $\endgroup$ Commented Oct 5, 2022 at 0:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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