# Efficiently find all connected subgraphs

Is there a way to generate all the connected subgraphs of a graph in mathematica without going through all the subsets of the nodes and checking if the subgraph is connected (which will be O(2^N)*O(checking_connectedness) ) ?

I wrote this code which finds the subgraphs of size 2 to n :

subs[g_,n_] :=
Select[
Subgraph[g, #]& /@ Subsets[VertexList[g], {2, n}],
ConnectedGraphQ]

• Are you looking for ConnectedComponents? – Daniel Lichtblau May 29 '15 at 16:53
• @DanielLichtblau I think he means that for the connected graph 1 - 2 - 3, the subgraphs induced by (1, 2) and (2, 3) are good solutions, but (1, 3) is not. I'd expect a huge number of solutions, which makes efficiency dubious ... but it's not an uninteresting problem. – Szabolcs May 29 '15 at 20:05
• To find connected subgraphs of size $k$, you could start from an arbitrary vertex, then traverse the graph along edges in all possible ways until you have reached $k-1$ other vertices. These are all good solutions. Then remove the starting vertex (as we have already found all connected subgraphs containing it) and repeat the procedure with another vertex. – Szabolcs May 29 '15 at 20:10
• Here's a paper on the topic which might be helpful: math.unl.edu/~shartke2/math/papers/k-subgraphs.pdf – Szabolcs Jun 15 '15 at 7:38
• You might be able to get a pretty good speed-up for an "average" graph by running it through ConnectedComponents first. For a graph whose largest connected component has $m$ vertices, this would require $\mathcal{O}(2^m)$ checks rather than $\mathcal{O}(2^n)$. – Michael Seifert Jun 15 '15 at 15:46

It is impossible to have an efficient algorithm for the problem, as the output can be of size $2^n$, where $n$ is the number of vertices. The worst case is realized by a complete graph on $n$ vertices.