This is a problem from the textbook "Algorithms, 4th edition" by Robert Sedgewick and Kevin Wayne.
4.3.26 Critical edges. An MST edge whose deletion from the graph would cause the MST weight to increase is called a critical edge. Show how to find all critical edges in a graph in time proportional to $E \log E$. Note: This question assumes that edge weights are not necessarily distinct (otherwise all edges in the MST are critical).
There is an algorithm (see below), as well as an accepted answer, at stackoverflow. However, in my opinion, the correctness proof is not complete because it does not justify that all critical edges can be found. Moreover, I cannot figure out how the time complexity of $O(m \log m)$ is achieved in this algorithm (given the hint in the answer).
The algorithm is (in my understanding):
- Run Kruskal algorithm on this graph. Whenever we encounter an edge $e$ whose insertion in the MST creates a cycle, the edges in this cycle with smaller weights than $w(e)$ will be reported as critical edges.
My questions are:
- How to prove the correctness of this algorithm: (1) all edges reported are critical edges; (2) all critical edges are reported?
- How to achieve $O(m \log m)$ with appropriate data structures?
- If this algorithm is wrong, how to solve the problem?