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?
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
5
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).
answered Jan 31, 2013 at 17:00
-
$\begingroup$ Thanks for the answer. Can we construct the tree by node extension? i.e., start with empty graph and start by adding nodes. $\endgroup$ Jan 31, 2013 at 18:55
-
$\begingroup$ 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? $\endgroup$ Jan 31, 2013 at 19:01
-
1$\begingroup$ 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. $\endgroup$ Jan 31, 2013 at 20:47
-
$\begingroup$ 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? $\endgroup$ Jun 30, 2018 at 23:46
-
$\begingroup$
$\endgroup$
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)}$.
