Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

minimum connected subgraph containing a given set of nodes

Tags:

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.

like image 485
hyluka Avatar asked Oct 20 '10 07:10

hyluka


People also ask

Is the maximum connected subgraph of a given graph?

A connected component is a maximal connected subgraph of an undirected graph. Each vertex belongs to exactly one connected component, as does each edge. A graph is connected if and only if it has exactly one connected component. The strong components are the maximal strongly connected subgraphs of a directed graph.

How many subgraphs does a connected graph on two vertices have?

In general, (n0)+(n1)+(n2)+⋯+(nn)=2n, so (n1)+(n2)+⋯+(nn)=2n−1.

Is a connected subgraph in which there are no cycles?

A connected acyclic graph is called a tree. In other words, a connected graph with no cycles is called a tree.

How many spanning subgraphs are there?

How many spanning subgraphs are there? There are 2n induced subgraphs (all subsets of vertices) and 2m spanning subgraphs (all subsets of edges).


2 Answers

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.

like image 185
Falk Hüffner Avatar answered Nov 17 '22 05:11

Falk Hüffner


I can't think of an efficient algorithm to find the optimal solution, but assuming that your input graph is dense, the following might work well enough:

  1. Convert your input graph G(V, E) to a weighted graph G'(N, D), where N is the subset of vertices you want to cover and D is distances (path lengths) between corresponding vertices in the original graph. This will "collapse" all vertices you don't need into edges.

  2. Compute the minimum spanning tree for G'.

  3. "Expand" the minimum spanning tree by the following procedure: for every edge d in the minimum spanning tree, take the corresponding path in graph G and add all vertices (including endpoints) on the path to the result set V' and all edges in the path to the result set E'.

This algorithm is easy to trip up to give suboptimal solutions. Example case: equilateral triangle where there are vertices at the corners, in midpoints of sides and in the middle of the triangle, and edges along the sides and from the corners to the middle of the triangle. To cover the corners it's enough to pick the single middle point of the triangle, but this algorithm might choose the sides. Nonetheless, if the graph is dense, it should work OK.

like image 33
Gintautas Miliauskas Avatar answered Nov 17 '22 04:11

Gintautas Miliauskas