2
$\begingroup$

Let's suppose we have a weighted and connected graph. We can easily find the minimum spanning tree for this graph. But let's say we want to "force" a certain edge $e$ to be in the MST. For doing so, we are allowed to remove some edges from the graph. But I don't want to remove too many edges. Is there an efficient algorithm that can find the minimum number of edges to remove before $e$ becomes a member of MST?

I am particularly interested in that minimum value, and not the edges to remove.

I think there is a way to find a spanning tree that contains $e$. All we have to do is to insert a dummy node between the two nodes that are connected by $e$. But I doubt this helps. Any hint would be appreciated.

Improve this question
$\endgroup$
4
  • $\begingroup$ Do you want to make sure that $e$ is in all or in some MST? $\endgroup$
    – Pål GD
    Jan 14 at 12:30
  • $\begingroup$ @PålGD just some MST would do it. $\endgroup$
    – Fish_n_Chips
    Jan 14 at 12:42
  • $\begingroup$ Which property must $e$ have to never be in any MST? $\endgroup$
    – Pål GD
    Jan 14 at 12:43
  • $\begingroup$ It must be the heaviest edge in some cycle. Am I right? @PålGD $\endgroup$
    – Fish_n_Chips
    Jan 14 at 12:47

1 Answer 1

Reset to default
1
$\begingroup$

An edge $uv$ is in some MST if and only if it is a minimum-weight edge of some cut. So we need to find a $uv$-cut with a minimum number of edges whose weight is strictly less than $w(uv)$. Once those edges are removed, $uv$ will be in some MST.

Algorithmically, any min $st$-cut algorithm, applied on the subgraph of edges of weight less than $w(uv)$, will give us the answer. For instance you can use a max $uv$-flow algorithm to find the cut, if you don't know fancier algorithms.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Your first paragraph is good, the second paragraph does a leap of faith and I don't think it's completely sound. $\endgroup$
    – Pål GD
    Jan 14 at 14:27
  • $\begingroup$ $K_{3,2}$ is a counter-example if you let one of the degree-2 vertices have both its edges weight 2 and the remaining edges have weight 1. Let $e=uv$ be an edge with weight 2. A minimum $uv$-cut is now for example edges with weight $2,1,1$. However, $e$ is actually already in an MST. $\endgroup$
    – Pål GD
    Jan 14 at 14:29
  • 1
    $\begingroup$ No, if $v$ is the degree-2 vertex whose incident edges have weight 2, the min $uv$-cut is $\delta(v)$, which is empty, in the graph of edges with weight $< 2$. $\endgroup$
    – Guyslain
    Jan 14 at 16:17

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.