2 of 3
Commonmark migration

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.

John L.
  • 39k
  • 4
  • 33
  • 90