6
$\begingroup$

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]
$\endgroup$
  • 2
    $\begingroup$ Are you looking for ConnectedComponents? $\endgroup$ – Daniel Lichtblau May 29 '15 at 16:53
  • $\begingroup$ @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. $\endgroup$ – Szabolcs May 29 '15 at 20:05
  • 3
    $\begingroup$ 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. $\endgroup$ – Szabolcs May 29 '15 at 20:10
  • 3
    $\begingroup$ Here's a paper on the topic which might be helpful: math.unl.edu/~shartke2/math/papers/k-subgraphs.pdf $\endgroup$ – Szabolcs Jun 15 '15 at 7:38
  • 2
    $\begingroup$ 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)$. $\endgroup$ – Michael Seifert Jun 15 '15 at 15:46
7
$\begingroup$

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.

That being said, your proposed algorithm achieves the bound, so it is optimal. That is, there can be other ways to write the algorithm, but the exponential sized output will always dominate the runtime.

$\endgroup$
  • $\begingroup$ With that being said, one might care about output-sensitive algorithms, see here. $\endgroup$ – Juho Jun 18 '15 at 12:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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