Find all critical edges for minimum spanning tree

Question

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?

Answer 1

Since Kruskal's algorithm sorts the edges according to their lengths, the trick here i to partition the edges into subsets of edges with equal lengths.

For each subset (in increasing order) check which components are being joined using each edge of this set before joining them. If two (separate) components are being joined using more than one edge of this subset then both (all) these edges are non critical (since we can choose any of them and still get a spanning tree).

Now we are visiting each subset (and accordingly each edge) two times, the complexity is still in $O(|E|)$ and we need an additional $\log$ for the DSU join operations.

However, you should be aware of the case where for example three edges $\epsilon_1,\ \epsilon_2,\ \epsilon_3$ of the same lengths joins components $V_1-V_2, V_2-V_3, V_3-V_1$ respectively, which makes non of them critical point since we can use any two of them and leave the third one. A solution of this problem is to add all this edges at first to the Graph, then you will have a non tree graph, with cycles in places where you had many choices, and that makes the critical edges exactly the Bridges (check the link) in this graph.

P.S since bridges can be found in $O(|V| + |E|)$ total runtime is still $O(|E|*\log|E|)$

Answer 2

The simplest and fastest algorithm

Here is a correct algorithm that finds all critical edges.

Input: a weighted connected undirected graph $G=(V, E)$.
Output: all critical MST edges.
Procedure:

1. Let $result$ be an empty list.
2. Make a disjoint-set data structure starting with $V$ with operations $\text{find}(\cdot)$ and $\text{union}(\cdot, \cdot)$. That is, each vertex will be represented by itself.
3. Sort all edges into blocks of edges of the same weight in strictly increasing order, $B_1, B_2, \cdots, B_k$. That is, edges in $B_1$ are of the same weight lighter than edges in $B_2$. Edges in $B_2$ are of the same weight lighter than edges in $B_3$. Etc.
4. For each block $B$ in $B_1, B_2, \cdots, B_k$, do:
   1. Create an empty graph $H$ and an empty map $\mathcal M$.
   2. For each edge $(u,v)$ in $B$,
      • if $\text{find}(u)$ is not a vertex of $H$, add it to $H$.
      • if $\text{find}(v)$ is not a vertex of $H$, add it to $H$.
      • if $\{\text{find}(u), \text{find}(v)\}$ is not an edge of $H$, add it to $H$ and let $\mathcal M$ map $\{\text{find}(u),\text{find}(v)\}$ to $\{u,v\}$.
   3. Find all bridges in $H$. This can be done as described at here or here.
   4. For each bridge $b$, add $\mathcal M[b]$ to $result$.
   5. For each edge $(u,v)$ in $H$, call $\text{union}(u,v)$.
5. Return $result$.

If $\text{find}(\cdot)$ and $\text{union}(\cdot,\cdot)$ and finding bridges are not implemented badly, this algorithm runs in $\mathcal O(E\log E)$.

An edge is critical iff it appears in every MST.

It is easy to prove the proposition above. What is returned by the algorithm above is, in fact, all edges that must appear in every MST.

Detailed analysis on the 3 questions of OP

Please see a previous version of this answer.