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?

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.

StackExchange Computer Science Q#101863, answer score: 2