2
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Won't removing all the heavy edges give us the minimum spanning tree? So if there was a linear solution for this problem, we would also have a linear solution for the minimum spanning tree problem. $\endgroup$ – Amir Nasr Jul 30 '16 at 12:23
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.