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?

  • 2
    $\begingroup$ 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. $\endgroup$
    – c.lorenz
    Commented Oct 22, 2013 at 19:58

1 Answer 1


[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$.

— Garey and Johnson, Computers and Intractability, Freeman, 1979. Citation is to private communication with E. R. Berlekamp.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.