Finding Minimum Weight Subgraph Spanning Tree

834 Views Asked by At

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?

1

There are 1 best solutions below

0
On BEST ANSWER

Your problem is a generalization of minimum Steiner tree that is an NP-hard problem and in general, there is no polynomial algorithm to solve it. More explanation can be found at Generalization of minimum Steiner tree