Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

What is the complexity of enumerating all connected induced subgraphs from an undirected graph.

Also, Is the complexity of enumerating all maximal connected induced subgraphs the same?

share|improve this question
add comment

2 Answers 2

It's not difficult to show that this is polynomial per subgraph, for the connected induced subgraphs. I don't know what you mean by a maximal connected induced subgraph; isn't that just a connected component? I also don't know what has been published on this problem.

One way to solve the problem is to define a tree structure on these subgraphs as follows: choose an arbitrary assignment of distinct weights to the edges of the input graph. Define the parent of a connected induced subgraph to be the graph formed by finding its minimum spanning tree, removing the leaf edge of maximum weight, and forming the induced subgraph of the remaining vertices. For a subgraph with only one vertex, define its parent to be the empty graph (which forms the root of the tree structure)

Reverse search (essentially, DFS of this tree) will then find each connected induced subgraph in time polynomial per subgraph. You can find the children of any node in the tree by trying all ways of adding one vertex and checking which of them would form the heaviest leaf of the MST of the augmented subgraph; finding all the children of a single node takes polynomial time, which is all that's required to make this work.

The family of connected subsets of vertices of a graph, with two subsets considered adjacent to each other if they differ in the addition or removal of a single vertex, forms a partial cube structure (see the first example in my book Media Theory) and similar reverse search ideas can be used to list all states in any such structure (detailed later in the book).

share|improve this answer
    
Thanks for the answer. Can we construct the tree by node extension? i.e., start with empty graph and start by adding nodes. –  user13539 Jan 31 '13 at 18:55
    
Thanks for the answer. Can the tree structure be constructed in a top down approach. Start with empty graph and then start by adding nodes? –  user13539 Jan 31 '13 at 19:01
1  
That top down approach is exactly what the reverse search ends up doing. But it's easier to define the tree bottom up before searching it top down. –  David Eppstein Jan 31 '13 at 20:47
add comment

This only complements David's answer, who shows that the number of connected induced subgraphs can be enumerated with polynomial delay. Since a complete graph on $n$ vertices has $2^n$ connected induced subgraphs there is no hope to obtain any algorithm faster than $2^n$ for general graphs. For bounded-degree graphs, however, slightly better bounds are known for the number of connected induced subgraphs. Björklund et al. (2012) show that any graph on $n$ vertices with maximum degree $\Delta$ has at most $(\beta_{\Delta})^n$ connected induced subgraphs, where $\beta_{\Delta} = (2^{\Delta+1} − 1)^{1/(\Delta+1)}$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.