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&nbsp;$C$ of&nbsp;$V$, find a subtree of&nbsp;$G$ with the least number of vertices to connect all the vertices in&nbsp;$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?
[Steiner tree] remains NP-complete if all edge weights are equal, even if $G$&nbsp;is a bipartite graph having no edges joining two vertices in&nbsp;$C$ or two vertices in&nbsp;$V-C$.


&mdash; Garey and Johnson, Computers and Intractability, Freeman, 1979.  Citation is to private communication with E.&nbsp;R. Berlekamp.