Algorithm for finding all the heaviest edges in a graph

Question

We have a non directed, not necessarily connected graph $G=(V,E)$, that is represented by a adjacency list, and a weight function $w:E \to R$. All edges have distinct weight. An edge is "heavy" if there exists a simple cycle in $G$ that contains it, and it has the maximal weight in that cycle. The question is to give an algorithm which finds all of the heaviest edges in $G$.

My proposed algorithm:

1. Create an array $A$ of size $|V|$ where every cell represents a node $v_i$ in G. Mark all nodes as 'unexplored'.
2. Select the node $v_1$ in $G$ and run Prim's MST algorithm from it. Modify Prim's algorithm so that when a node is reached by the MST tree it is marked as 'explored' in $A$.
3. Scan the array $A$ linearly from the last node encountered as 'unexplored'. Each time a node marked 'unexplored' is found, do step 2 for it.
4. When $A$ is traversed completely, mark the group of all the edges in all the MSTs found as $E'$.
5. Return $E/E'$ — this is the group of heaviest edges.

The algorithm's correctness follows from the cycle property for MSTs, and that every edge has a distinct weight.

This algorithm is as efficient as running Prim's MST algorithm on a connected non directed graph — that is $O(E + V \lg V)$ with Fibonnaci heaps.

My questions is, is this is the optimal running time for this problem? I have a feeling this can somehow be done in linear time using DFS.

Answer 1

In line with what Amir Nasr said in his comment above, I think the cycle property of MSTs would imply that finding a solution to your problem in linear time would find an MST in linear time.

From the Wikipedia page on MSTs and a few of the specific algorithms, it seems you can only currently do better be exploiting specific properties of your graph or using randomness.

You may find the $O(\left\vert{E}\right\vert\log{}\left\vert{V}\right\vert)$ complexity preferable to the $O(\left\vert{E}\right\vert+\left\vert{V}\right\vert\log{}\left\vert{V}\right\vert)$, and it seems that would just require a different choice of data structures or using either Kruskal's or Borůvka's.

For complexity with no $\log{}$ factors, it seems (for lack of a known general linear, deterministic, MST algorithm) you need either dense graphs, integer weights, or to use the expected linear time MST algorithm below.

https://en.wikipedia.org/wiki/Expected_linear_time_MST_algorithm