1
$\begingroup$

The complete question is as follows:

An edge of a flow network is called critical if decreasing the capacity of this edge results in a decrease in the maximum flow. Give an efficient algorithm that finds a critical edge in a network.

I believe some variation of Ford-Fulkerson would have to be used over here, however I am not too sure. Also I am a little confused by the wording of the question. What does efficient mean? In linear time i.e. $O(|V| + |E|)$?

Improve this question
$\endgroup$
2
  • $\begingroup$ We require you to credit the source of all material originally written by others: cs.stackexchange.com/help/referencing $\endgroup$
    – D.W. ♦
    Aug 14, 2022 at 4:59
  • $\begingroup$ You might find this page helpful in improving your question. $\endgroup$
    – D.W. ♦
    Aug 14, 2022 at 5:00

1 Answer 1

Reset to default
1
$\begingroup$

By the max-flow min-cut theorem the (maximum) flow $f$ between two vertices $s$ and $t$ in the network is equal to the overall weight of the edges in a minimum $s$-$t$-cut $C$.

The means that it suffices to find a minimum $s$-$t$-cut $C$ and return any edge $e \in C$ (decreasing the capacity $e$ reduces the weight of the minimum cut and hence the flow from $s$ to $t$).

A way to find $C$ using again the relation with the maximum flow is as follows: find a maximum flow from $s$ to $t$ (using the algorithm of your choice) and let $S$ be the set of saturated edges, i.e., edges such that the flow across them matches their capacity. Choose $C$ as the set of all edges $(u,v)$ such that $u$ is reachable from $s$ and $v$ can reach $t$ in $G-S$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Can we use the residual graph to get $C$? $\endgroup$
    – Jash Shah
    Aug 14, 2022 at 17:09
  • 1
    $\begingroup$ The saturated edges of $G$ are exactly those that are not in the residual graph $G'$. Still, you cannot simply pick $C$ as all edges in $G-G'$ since this set might be too big (think for example of a graph $G$ consisting of a single path from $s$ to $t$ where all edges have the same capacity). However the set of vertices reachable from $s$ in $G-S$ is exactly the set of vertices reachable from $s$ in the residual graph $G'$. Similarly, the set of vertices that can reach $t$ in $G-S$ are exactly those that can reach $t$ in $G'$, so you can simply perform two visits on $G'$ to discover $C$. $\endgroup$
    – Steven
    Aug 14, 2022 at 21:40

Your Answer

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

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