# Steiner tree problem for unweighted graphs

Steiner tree problem for weighted graphs is NP-hard. How about unweighted graphs? That is, given a graph $G=(V,E)$ and a subset $C$ of $V$, find a subtree of $G$ with the least number of vertices to connect all the vertices in $C$. (Since we are looking for a subtree, minimizing the number of vertices also minimizes edges.) The unweighted Steiner tree problem should be NP-hard but is there any better (approximation) algorithm for it?

• There is a (constant-)approximation-preserving reduction from the weighted case to the unweighted: if the weights are at most polynomial, simply subdivide edges into unweighted paths of the same length (if not, it still seems doable at a subconstant loss in approximability). Consequently, the approximability of the unweighted case is the same as the weighted, where there are constant approximability and inapproximability results. Commented Oct 22, 2013 at 19:58

[Steiner tree] remains NP-complete if all edge weights are equal, even if $G$ is a bipartite graph having no edges joining two vertices in $C$ or two vertices in $V-C$.