2
$\begingroup$

I have a problem where I am supposed to analyze the Steiner tree problem by doing the following 3 steps.

1) Look up what the Steiner tree problem is.

2) Find a polynomial time reduction to it from one of these 8 known NP-complete problems:

  • 3-col
  • subset-sum
  • clique
  • hampath
  • Uhampath
  • sat
  • 3-sat
  • vertex-cover.

3) Prove that it is NP-complete.

My first problem is that I don't understand what the Steiner tree problem is. I can't find the problem anywhere. Wikipedia has a page on it, but doesn't really describe it in simple terms.

Can anyone help me out on this, and also give me hints for number 1, 2 and 3?

Improve this question
$\endgroup$
3
  • $\begingroup$ You can think of the Steiner tree problem as a generalization of the MST problem. The difference is that you specify a subset of vertices you want connected, rather than the entire set $V$. $\endgroup$
    – Nicholas Mancuso
    Mar 26, 2013 at 0:51
  • $\begingroup$ Seems origin of this problem is by Fermat, when he proposed finding a point to minimize total distance from that point to three given point in Euclidean space (center of triangle), for more simple (or harder) definitions I'd suggest you to read the book that I linked below (at least preface and start of chapter one), but note that edges of graph are weighted not necessary same weight and in most case is in metric space. books.google.de/books?id=NK4hUPfKZh8C&pg=PA1 $\endgroup$
    – user742
    Mar 26, 2013 at 10:53
  • $\begingroup$ In which way is the Wikipedia description confusing you? I think it's fairly straight-forward. $\endgroup$
    – Raphael ♦
    Mar 26, 2013 at 11:22

1 Answer 1

Reset to default
6
$\begingroup$

Short answer: You are given a graph with some special vertices, and are asked to connected them using as few (or cheap) edges as possible. By connecting them, we mean that you will use only those edges.

More formally, you are given a graph $G = (V,E)$ and a set $S \subseteq V$ of vertices. These vertices are often refered to as terminals. You are also given some number $k \in \mathbb{N}$.

I ask you now: Can you find a set of edges $F \subseteq E$ such that (a) $|F| \leq k$ and (b) in the graph $G' = (V, F)$, $S$ belongs to the same connected component.

Now, if such a set $F$ exists and you take a subset minimal $F'$, the graph $G' = (V,F')$ is a forest, and the component containing $S$ is called a Steiner tree.

This is the unweighted decision version. It is not hard to come up with the optimization or weighted version. The weights are on the edges.

Edit: When it comes to your next question, I would go for Vertex Cover. Hint: Subdivide every edge and make the new vertices the terminals. Then the number of edges in a Steiner tree is some function of the $E$ and the number of vertices in the vertex cover in the original graph.

And to show that the problem is in NP should be quite easy.

Improve this answer
$\endgroup$
9
  • $\begingroup$ Your formal definition I find complicated to understand. So here is what I understand so far, is this right? Given a graph G(V,E) where some subset of V is marked special. You need to remove all nodes and edges from G such that only the special marked nodes remain and are connected by edges? I don't think I am right, but maybe if you could link some visuals and explain using those, that would be great. $\endgroup$
    – omega
    Mar 26, 2013 at 1:41
  • $\begingroup$ @omega Take $G$, and make all edges red. Some vertices of $G$ are marked special. Now start turning red edges into green edges. You want to find the least number of edges you need to turn green to make the special vertices connected. That is, you have to have a "green path" between every pair of special vertices. $\endgroup$
    – Juho
    Mar 26, 2013 at 2:54
  • $\begingroup$ Do you mean that you need to turn the minimum amount of red edges to green edges such that for every two marked special nodes A and B, there exists a green edged path from A to B? Then the steiner tree is the graph of G but only the marked special nodes and the green edges? $\endgroup$
    – omega
    Mar 26, 2013 at 3:51
  • 1
    $\begingroup$ @omega Yes, but you can have other vertices in the Steiner tree too. For example, it might be that you can't connect two special vertices without including some "intermediate" nodes. $\endgroup$
    – Juho
    Mar 26, 2013 at 4:25
  • $\begingroup$ So to do a reduction from vertex cover, basically if you can find a vertex cover of any arbitrary graph, then you mark the nodes of the vertex-cover to be the specially marked nodes, then it is the Steiner tree problem? $\endgroup$
    – omega
    Mar 26, 2013 at 19:35

Your Answer

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

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