3
$\begingroup$

I have the following question in a homework:

Let $G = (V,E)$ be an undirected graph, and let $$A = \{ e \in E \mid \text{ s.t. exists an MSP $T$ containing } e\}.$$

We were asked to find $A$ in $O(m \log n)$ time.

Any suggestions?

$\endgroup$
2
  • 1
    $\begingroup$ You don't write anything about weights, but I assume that the graph is weighted? $\endgroup$
    – Pål GD
    Commented Jan 22, 2020 at 15:45
  • 1
    $\begingroup$ Can you clarify what an MSP is? Should it be MST? $\endgroup$
    – Juho
    Commented Jan 22, 2020 at 17:23

1 Answer 1

1
$\begingroup$

We call an edge superheavy if it is the unique heaviest edge in some cycle. This post shows that an edge $e\in A$ if and only if $e$ is not superheavy.

To find all edges that are not superheavy, we can first sort the edges according to their weights from small to large. Then, we remove all edges, re-add them in this order, and track the connected components by a disjoint-set data structure.

Now we can check whether an edge $e$ is superheavy by checking whether it connects two vertices in different connected components in the graph with edges whose weights are less than $w(e)$: If $e$ is superheavy, then the two endpoints of $e$ are connected by a path on which the edges have weights less than $w(e)$, so the two endpoints must lie in the same connected components in the graph with edges whose weights are less than $w(e)$. On the other hand, if $e$ connects two vertices in the same connected components in the graph with edges whose weights are less than $w(e)$, then we can find a path connecting the two endpoints of $e$ on which the edges have weights less than $w(e)$, so $e$ along with this path forms a cycle and $e$ has the largest weight in this cycle, so $e$ is superheavy.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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