Find critical edges of an MST: possible with modified Prim's algorithm?

Question

I came across this question while finding a solution for a "critical edge" problem. The original (C++) problem, which I have already solved, was:

Consider a graph G=(V,E). Find how many edges belong to all MSTs, how many edges do not belong to any MST and how many edges belong to some MSTs, but not all.

Let's call "green", "red" and "yellow", respectively, the edges in the 3 above cases.

After conducting my research, I came across Find all critical edges of an MST, which solves the problem. One would run a modified version of Kruskal's algorithm: if two or more edges of the same weight connect the same components, thus forming a cycle, then all these are yellow edges, i.e., edges that could be included in the MST (or not). Edges that have been indisputably selected are "green" and edges that create a cycle in the same component are "red". So, the original problem has been solved.

The issue with the above algorithm is that it runs in O( |E| * log|V| ), which is the running time of Kruskal's algorithm (please correct me if I'm wrong). I was considering whether a modified version of Prim's algortihm could also be used, as it has a better amortized complexity of O( |E| + |V| log |V| ), if a Fibonacci heap is used.

My feeling is that a modified version of Prim's algorithm cannot be used here, since we are obliged to iterate all edges based on ascending weight; however, I cannot prove this. So, it is possible to further reduce the complexity of this problem?

Answer 1

This problem is easier than the problem of sensitivity analysis of minimum spanning trees, which is to determine how much each tree/nontree edge can increase/decrease in weight before the minimum spanning tree changes. The best known algorithm for MST sensitivity analysis appears to be due to Seth Pettie (2005, arXived 2014), with a running time of O(|E| log alpha(|E|, |V|)). This is very close to optimal (alpha is inverse Ackermann) but also still superlinear. Several randomized algorithms with linear expected running times are known.