minimum connected subgraph containing a given set of nodes

algorithm graph graph-theory subgraph graph-algorithm
hyluka picture hyluka · Oct 20, 2010 · Viewed 7.7k times · Source

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.

Answer

Falk Hüffner picture Falk Hüffner · Oct 20, 2010

This is exactly the well-known NP-hard Steiner Tree problem. Without more details on what your instances look like, it's hard to give advice on an appropriate algorithm.

Related questions

Cycles in an Undirected Graph

Given an undirected graph G=(V, E) with n vertices (|V| = n), how do you find if it contains a cycle in O(n)?

Read More
Difference between hamiltonian path and euler path

Can some one tell me the difference between hamiltonian path and euler path. They seem similar!

Read More
How to remove cycles in an unweighted directed graph, such that the number of edges is maximised?

Let G be an unweighted directed graph containing cycles. I'm looking for an algorithm which finds/creates all acyclic graphs G', composed of all vertices in G and a subset of edges of G, just small enough to make G' …

Read More