# Polynomial Time Algorithm for Steiner Tree Problem

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?

• 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$? – John L. Dec 21 '18 at 7:52
• 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 – Null Pointer Dec 21 '18 at 8:03

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.

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