minimum connected subgraph containing a given set of nodes

user_481398 0
Viewed 9271

I have an unweighted, connected graph. I want to find a connected subgraph that definitely includes a certain set of nodes, and as few extras as possible. How could this be accomplished?

Just in case, I'll restate the question using more precise language. Let G(V,E) be an unweighted, undirected, connected graph. Let N be some subset of V. What's the best way to find the smallest connected subgraph G'(V',E') of G(V,E) such that N is a subset of V'?

Approximations are fine.

subgraph graph-theory graph-algorithm graph algorithm
5 Answers

As already pointed out, this is the Steiner tree problem in graphs. However, an important detail is that all edges should have weight 1. Because |V'| = |E'| + 1 for any Steiner tree (V',E'), this achieves exactly what you want. For solving it, I would suggest the following Steiner tree solver (to be transparent: I am one of the developers):

https://scipjack.zib.de/

For graphs with a few thousand edges, you will usually get an optimal solution in less than 0.1 seconds.

user_113390200
Related