Finding Bottleneck Edges in a Graph in O(V+E)

Question

First off, I would like to clarify that I've seen this: Finding 'bottleneck edges' in a graph

And it's not a duplicate of that, just an unfortunate coincidence that the person mistakenly called a min-cut a "bottleneck."

A bottleneck edge is an edge in a flow network that, on being increased, increases the maximum flow of the network.

So this isn't necesarrily the min-cut, as in the case of a graph like o-1->o-1->o, we have no bottleneck edges but we do have a min cut.

(In that example, o's are nodes and an edge is -*->, where * is some integer.)

Anyway, so finding all bottlenecks can apparently be done in O(V+E), (assumed that the graph is given in adjacency list representation) and I think that the way to do it would be to create two arrays of size V, which I will call INCOMING and OUTGOING, then iterate through each element of the adjacency list twice, the first time increasing INCOMING[i] by the value of the edges going into each node, and the second time increasing OUTGOING[j] by the value going out of each node, where j is the node which adjacency list we're reading, and i is the node which edge is going to it in the adjacency list.

I think this works in O(V+E) time, but I feel like my solution is definitely more convoluted and hard to explain. Is there a better solution (not better than O(V+E), but just more simple?)

Answer 1

You could still use the Ford-Fulkerson algorithm for this problem. Basically, finish iterating over the graph until you're left with the final (disconnected) residual graph. Now, there will be a set of nodes which are reachable from the source S. And there will be a separate set of nodes which are reachable from the sink T.

Any edges that connect the first set of nodes to the second set of nodes, will be bottleneck edges.

Why is this correct? Just imagine if you increased the capacity of one of these edges, then the final residual graph you got in step 1 would no longer be the final residual graph, and there would still be one more possible iteration of the ford-fulkerson algorithm.