5
$\begingroup$

I am trying to find an algorithm which would check for each edge in a given weighted undirected graph whether it belongs to any of the graph's Minimum Spanning Trees.

I have found many potential solutions to this problem, which use the cycle property of MSTs, that is (quoting Wikipedia): For any cycle C in the graph, if the weight of an edge e of C is larger than the individual weights of all other edges of C, then this edge cannot belong to a MST.

It is obvious to me how this property can be used to determine which edges can definitely not belong to any of the graph's MTSs, but I have doubts if the inverse of the cycle property is also true, that is if: For every cycle C in the graph, if the weight of an edge e of C is less or equal to the individual weight of any other edge of C, then this edge belongs to at least one MST.

In other words, is edge e not being the heaviest edge in every cycle containing e only a necessary condition, or a sufficient condition to e belonging to an MST?

If the above is false, then all I would want to see is a counterexample. If however this is true, could anybody prove why it is so?

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ Have you tried proving or disproving the inverse of the cycle property? Where did you get stuck? $\endgroup$ – Yuval Filmus Jul 14 '16 at 21:26
  • $\begingroup$ At first intuition led me to believe the inverse of the cycle property is not always true, however I have so far failed to come up with a counterexample, which makes me think this hunch should not be trusted :) $\endgroup$ – F.K. Jul 14 '16 at 21:56
  • $\begingroup$ Oh is the inverse always true because if it were not, it would mean that there could exist such an edge e belonging to cycle C, which is not of a unique and maximal weight for that cycle, and still has a path of smaller weight connecting it to the spanning tree, which would in turn mean there must exist such a cycle in which it is the maximum weight edge (as we are not considering negative weights), which leads to a contradiction? $\endgroup$ – F.K. Jul 14 '16 at 22:14
4
$\begingroup$

If you want to test whether a specific edge belongs to some MST, you can use the following property.

Claim. An edge $e$ belongs some MST if and only if for every $\epsilon > 0$, if we reduce the weight of $e$ by $\epsilon$ then it belongs to all MSTs.

Proof. We first show that if $e$ belongs to some MST then for every $\epsilon > 0$, if we reduce the weight of $e$ by $\epsilon$ then it belongs to all MSTs.

Suppose that MSTs in the original graph have weight $w$. When we decrease the weight of $e$ by $\epsilon$, only trees containing $e$ have decreased weight. Since $e$ belongs to some MST, the new graph has MSTs of weight $w - \epsilon$, and all of them contain $e$.

We complete the proof by showing that if $e$ doesn't belong to any MST then for small enough $\epsilon > 0$, if we decrease the weight of $e$ by $\epsilon$ then $e$ still belongs to no MST. Indeed, suppose that MSTs in the original graph have weight $w$, and the lightest spanning tree containing $e$ has weight $w+\delta$ for $\delta > 0$. If we decrease the weight of $e$ by less than $\delta$, it still belongs to no MST. $\qquad \square$

I'll let you figure out how to use the claim to test whether $e$ belongs to some MST; it suffices to find one MST in one graph. The same approach seems wasteful if you want to test all edges. I'll leave you to ponder whether any optimization is possible in that case.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thank you very much. Does the optimization you have in mind still use the cycle property, or are you suggesting to approach this problem from a completely different angle, for instance using Kruskal's algorithm with union-rep? $\endgroup$ – F.K. Jul 14 '16 at 22:20
  • $\begingroup$ I don't have any optimization in mind, but I bet one exists. $\endgroup$ – Yuval Filmus Jul 15 '16 at 4:44
1
$\begingroup$

Yuval Filmus's ingenious answer, which shows a way to test whether a specific edge belongs to some MST, does not answer OP's question and request. The question is whether edge $e$ not being the heaviest edge in every cycle containing $e$ only a necessary condition, or a sufficient condition to $e$ belonging to an MST. The request is a counterexample or a proof.

Here is my positive answer with proof, where I have actually proved that an edge is not in any MST if and only if it is is the unique heaviest edge in some cycle. In another word, for any edge $e$, $e$ is not the unique heaviest edge in any cycle if and only if $e$ belongs to an MST.

Here is a closely-related interesting fact. For any edge $e$, $e$ is not a heaviest edge in any cycle if and only if $e$ belongs to every MST. Together with the positive answer, this fact implies immediately the claim in Yuval Filmus's ingenious answer: An edge $e$ belongs some MST if and only if for every $ϵ\gt0$, if we reduce the weight of $e$ by $ϵ$ then it belongs to all MSTs.

|cite|improve this answer
$\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.