# 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? May 29, 2015 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. May 29, 2015 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. May 29, 2015 at 20:10
• Here's a paper on the topic which might be helpful: math.unl.edu/~shartke2/math/papers/k-subgraphs.pdf Jun 15, 2015 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)$. Jun 15, 2015 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.