Finding Minimum Weight Subgraph Spanning Tree

Question

Suppose we have a graph $G = (V, E, w:e\in E \to x \in \{0,1\})$. That is, a set of vertices, a set of edges and a weight function that assigns edges weights of 0 or 1.

Suppose we also have a subset of vertices $S \subset V$ and that we want to find a minimum-weight tree that spans the vertices in $S$. Since the vertices in $S$ might not be directly connected, we are allowed to use vertices in $V$ that may not be in $S$ to build our minimum-weight tree.

Is there an algorithm similar to Prim's or Kruskal's that we can use to solve this?

Answer 1

No, it's highly unlikely there is a polynomial time algorithm for this problem. The problem you describe is known as Steiner tree, and it is NP-hard. Moreover, it is computationally quite difficult from many other viewpoints as well.

A classical dynamic programming approach is the Dreyfus-Wagner algorithm running in $O^*(3^k)$ time, where $k$ is the number of terminals (i.e., the size of the set of pairs $S$ in your terminology). There is a lot of literature on the problem, so you might want to look at it from a particular viewpoint.