# 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. – c.lorenz Oct 22 '13 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$.