algorithmnetwork-flowminimum-cut

Critical Edges and Bottleneck Edges in a Flow Network (Max-Flow/Min-Cut Problem)

A critical edge in a flow network G = (V,E) is defined as an edge such that decreasing the capacity of this edge leads to a decrease of the maximum flow. On the other hand, a bottleneck edge is an edge such that an increase in its capacity also leads to an increase in the maximum flow in the network. Are all critical edges also bottleneck edges? I am having trouble proving this or giving a counterexample.

I would appreciate any help on this!

Solution

  • Nope

    Consider a simple graph: 1 -> 2 -> 3 in which both edges have the same weight. Both of these edges are critical, but neither is a bottleneck.