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

This answer will follow the question closely.

"However, in my opinion, the correctness proof is not complete because it does not justify that all critical edges can be found". Indeed, the accepted answer at stackoverflow 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)". Indeed, it requires some careful analysis to verify that complexity is achieved.

"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."

It turns out the algorithm in OP's understanding as above is not correct. For example, let graph $G$ have edge $AB, BC, CD, DA$ of weight 1 and edge $AC$ of weight 2. That algorithm will reported several critical edges while, in fact, $G$ has no critical edges.

Here is the original algorithm in my understanding.

Run the Kruskal's algorithm. But whenever we encounter an edge whose insertion in the MST creates a cycle and if that cycle already contains an edge with the same edge weight, then, the edge already inserted will not be a critical edge (otherwise all other MST edges are critical edges) that existing edge will be marked as a non-critical. At the end of the algorithm we obtain an MST. Any edge in that MST that is not marked as non-critical is reported as a critical edge. Thus we find all critical edges.

Well, the stricken text is in the original writing. The text following it is my understanding of it, which should be much clearer.

"How to prove the correctness of this algorithm:
(1) all edges reported are critical edges;
(2) all critical edges are reported?"

We will only refer to the version in my understanding as the algorithm. Fact (1) has been proved correctly by that accepted answer at stackoverflow, which says that in another run of Kruskal's algorithm on the graph with $e$ deleted $e$'s role in the MST will be replaced by a heavier edge if $e$ is not a bridge(this "if" condition is missing from that accepted answer, though).

Fact (2) has NOT been proved clearly anywhere as far as I can see. Before we prove fact (2), let us make some important preparation.

To be rigorous, let us use the clearer definition of a critical (MST) edge below that explicitly include all bridges.

An edge whose deletion from the graph will split the graph into two disconnected parts or cause the MST weight to increase is called a critical edge.

Please check that a critical edge as defined above must be in some MST. That is, a critical edge must be an MST edge. Also, all related writing I have seen treat bridges as critical edges either explicitly or implicitly. So this definition is just a clarification of the original definition in section 4.3.26 of the book "Algorithms, 4th edition" as quoted in the question. Please note that an edge that is not a critical edge may be in some MST or it may never be in any MST. That is, a non-critical edge can be either an MST edge or a non-MST edge.

(Theorem One on critical edges) An edge $e$ is a critical edge if and only if no cycle can contain $e$ as (one of) its heaviest edge(s).

Only the "only if" part is needed for this answer. However, a proof for "if" part is included as well just for completeness.

"If" part: Let $e$ be such that no cycle can contain $e$ as its heaviest edge. If $e$ is a bridge, then by definition $e$ is critical and we are done. Now assume $e$ is not a bridge. Let $m$ be an MST. Then $m$ must contains $e$. Let us delete $e$ from $G$ to obtain a new graph $G'$. $m$ is split into two parts, $m_1$ and $m_2$. Find a lightest edge $e'$ that connects $m_1$ and $m_2$. Then $m'=m_1\cup m_2\cup\{e'\}$ is an MST of the new graph $G'$. Suppose $e$ has its vertex $v_1$ in $m_1$ and $v_2$ in $m_2$. $e'$ has its vertex $v_1'$ in $m_1$ and $v_2'$ in $m_2$. Consider the cycle from $v_1$ to $v_2$ by $e$, from $v_2$ to $v_2'$ in $m_2$, from $v_2'$ to $v_1'$ by $e'$, from $v_1'$ to $v_1$ in $m_1$. Since $m$ is an MST of $G$, $e'$ is a heaviest edge in this cycle. Since $e$ is not a heaviest edge in any cycle, $e$ is lighter than $e'$. So the weight of $m'$ is larger than the weight of $m$. That is, $e$ is a critical edge and we are done.
"Only if" part: Let edge $e$ be such that there is a cycle $C$ that contains $e$ as its heaviest edge. If $e$ is not in any MST, then $e$ is not a critical edge and we are done. Now Let $m$ be in MST $m$. $m$ is separated by $e$ into two disjoint parts, $m_1$ and $m_2$. As a cycle that connects $m_1$ and $m_2$ at $e$, $C$ also contains another edge $e'$ that connects $m_1$ and $m_2$. Since $m$ is an MST, $e'$ is a heaviest edge in $C$. Since $e$ is also a heaviest edge in $C$, $e$ is as heavy as $e'$. That means the spanning tree $m_1\cup m_2\cup\{e'\}$, weighing the same as $m$, is also an MST and, hence, also an MST of $G$ after the deletion of $e$ $G$. That is, $e$ is not a critical edge.

Now, let us prove Fact (2). Every edge that is not reported as critical by the algorithm is of one of the following two kinds. The first kind of edges are not included in the MST (obtained at the end of the algorithm). The second kind of edges are selected in the MST and marked as non-critical because each of them is in a cycle created by the insertion of an edge of the same weight into the selected MST edges so far. Because Kruskal's algorithm processes the edges in the order of decreasing weights until we get a spanning tree, we can see easily that every edge of either kind is a heaviest edge in some cycle. According to the above characterization of critical edges, every edge that is not reported as critical by the algorithm is indeed not a critical edge. That is, every critical edge must have been reported as critical by the algorithm.

"How to achieve $O(m\log m)$ with appropriate data structures?"
Now let us come to the time complexity of the algorithm. To achieve the time complexity of $O(m\log m)$, we actually need another answer at stackoverflow, which specifies a refined version of the above algorithm that can find those non-critical MST edges faster. Readers who are interested in time complexity should check that fine answer and comments thereof.

Finally, Readers are invited to enjoy and prove two other characterizations of the critical edges.

(Theorem Two on critical edges) An edge $e$ is a critical edge if and only if $e$ is the unique lightest edge to cross some cut.

(Theorem Three on critical edges) An edge $e$ is a critical edge if and only if $e$ is contained in every MST.