0
$\begingroup$

Let $G=(V,E)$ be a connected graph, and let $S\subset V$. How to find a minimum subset $H\supset S$,and $G(H)$ is a connected graph.

It seems different from Steiner tree problem. Since in Steiner tree problem, the weight is added in edges and the goal is to find a tree. While in our problem, the goal is to find a induced subgraph.

$\endgroup$
1
  • $\begingroup$ This seems like a generalised path-finding algorithm, which would be the special case $|S|=2$. $\endgroup$
    – Arthur
    Sep 17 '17 at 11:32
1
$\begingroup$

Your problem is as hard as the Steiner tree problem for unweighted graphs. $G(H)$ might contain cycles, but a solution $H$ for your problem is a solution for the unweighted Steiner tree problem, since $G(H)$ is connected and therefore contains a spanning tree.

The Steiner Tree problem remains NP-complete even for unweighted graphs. See this question for details Steiner tree problem for unweighted graphs.

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