1
$\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$
0
$\begingroup$

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

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