# How to find a crticial edge in a flow network?

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|)$$?

• We require you to credit the source of all material originally written by others: cs.stackexchange.com/help/referencing
– D.W.
Aug 14, 2022 at 4:59
– D.W.
Aug 14, 2022 at 5:00

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$$.
• Can we use the residual graph to get $C$? Aug 14, 2022 at 17:09
• 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$. Aug 14, 2022 at 21:40