<p>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.</p>

<p>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)</p>

<p>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.</p>

<p>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 <a href="http://en.wikipedia.org/wiki/Partial_cube">partial cube</a> structure (see the first example in my book <em>Media Theory</em>) and similar reverse search ideas can be used to list all states in any such structure (detailed later in the book).</p>

CC BY-SA 3.0
2013-01-31T18:55:01.087Z
Thanks for the answer. Can we construct the tree by node extension? i.e., start with empty graph and start by adding nodes.
user13539
CC BY-SA 3.0
2013-01-31T19:01:38.390Z
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
CC BY-SA 3.0
2013-01-31T20:47:44.277Z
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
CC BY-SA 4.0
2018-06-30T23:46:01.773Z
There seems to be some ambiguity here when trying to compute the parent of a subgraph with two vertices -- removing the leaf edge of maximum weight gives two isolated vertices. Which one is the parent?
Elle Najt
CC BY-SA 4.0
2018-07-01T21:18:00.637Z
Choose one arbitrarily.
David Eppstein
CC BY-SA 3.0
2013-01-31T17:00:29.473Z
2013-01-31T17:06:01.740Z
2013-01-31T17:06:01.740Z
David Eppstein
<p>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. <a href="http://dx.doi.org/10.1145/2151171.2151181">Björklund et al. (2012)</a> 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)}$.</p>

CC BY-SA 3.0
2013-02-02T06:44:07.673Z
2013-02-02T06:44:07.673Z
Serge Gaspers
<p>What is the complexity of enumerating all connected induced subgraphs from an undirected graph.</p>

<p>Also, Is the complexity of enumerating all maximal connected induced subgraphs the same?</p>

<cc.complexity-theory><graph-theory><graph-algorithms>
enumerating all connected induced subgraphs
user13539
# enumerating all connected induced subgraphs

(Asked by: username_0 on 2013-01-31)

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?

**Tags:** cc.complexity-theory, graph-theory, graph-algorithms

---

## 2 answers

### Answer by username_1 on 2013-01-31. Score: 12

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](http://en.wikipedia.org/wiki/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).

> **Comments:**
> **username_0**: Thanks for the answer. Can we construct the tree by node extension? i.e., start with empty graph and start by adding nodes.  
> **username_0**: 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?  
> **username_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.  
> **username_2**: There seems to be some ambiguity here when trying to compute the parent of a subgraph with two vertices -- removing the leaf edge of maximum weight gives two isolated vertices. Which one is the parent?  
> **username_1**: Choose one arbitrarily.  

---

### Answer by username_3 on 2013-02-02. Score: 7

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)](http://dx.doi.org/10.1145/2151171.2151181) 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)}$.


---

