3
$\begingroup$

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?

$\endgroup$
  • 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 Oct 22 '13 at 19:58
6
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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