2
$\begingroup$

I know about Steiner Tree Problem. It is stated as

Input to Steiner Tree Problem is a weighted graph G and a subset T of the nodes (called terminal nodes) and goal is to find a minimum weight tree that spans all the nodes in T.

Can we give a polynomial time algorithm to solve the Steiner Tree Problem such that |T| ≥ n−1 where n is the number of nodes in the original graph. I've done a lot of RnD on it but it is still confusing. Can any one help me out?

$\endgroup$
  • $\begingroup$ Do you mean, given a weighted graph $G$ with $n$ nodes and a subset $T$ of nodes whose cardinality is no less than $n-1$, can we find a polynomial time algorithm that finds a minimum weight tree that spans all nodes in $T$? $\endgroup$ – Apass.Jack Dec 21 '18 at 7:52
  • $\begingroup$ Yes.. I found a paper on it where it is just stated that we can do it but no any further explanations or proofs were there.. so I just wanted to confirm it $\endgroup$ – Null Pointer Dec 21 '18 at 8:03
2
$\begingroup$

Yes, given a weighted graph $G$ with $n$ nodes and a subset $T$ of nodes whose cardinality is no less than $n−1$, there is a polynomial time algorithm that finds a minimum weight tree that spans all nodes in $T$.

Here is a simple algorithm.

  • Find a minimum-weight spanning tree $M$ of $G$. This is can be done by Kruskal's algorithm in $O(E\log E)$ time-complexity.

  • If $|T|=n$, return $M$.

  • Otherwise, $|T|=n-1$. There is exactly one node of $G$ that is not in $T$. Let it be node $v$. Removing node $v$ and all edges incident to $v$ from $G$, we obtain a graph $G'$. Note that $T$ is the set of all nodes of $G'$. Find a minimum-weight spanning tree $M'$ of $G'$, using Kruskal's algorithm again. If the weight of $M$ is smaller than that of $M'$, return $M$; otherwise, return $M'$.

I will let you check that the above algorithm is correct with polynomial time complexity. It should be easy enough.


Exercise. When $|T|=n-1$, what does it mean if $M$ is returned instead of $M'$?

Exercise. Show that if $|T|\ge n-k$ for some constant $k$ instead of $|T|\ge n-1$, the same conclusion holds.

$\endgroup$
  • $\begingroup$ Thank you so much. I will definitely give it a try by solving your exercise. $\endgroup$ – Null Pointer Dec 21 '18 at 18:37

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.