<blockquote>
  <p>[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$.</p>
</blockquote>

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

CC BY-SA 3.0
2013-10-22T14:32:03.180Z
2013-10-22T14:32:03.180Z
David Richerby
<p>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?</p>

CC BY-SA 3.0
2013-10-22T19:58:18.890Z
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
<graph-theory><approximation-algorithms><tree>
Steiner tree problem for unweighted graphs
notbad
# Steiner tree problem for unweighted graphs

(Asked by: username_0 on 2013-10-22)

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?

**Tags:** graph-theory, approximation-algorithms, tree
> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2013-10-22. Score: 6 | Accepted answer

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


---

