3
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

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