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]
Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ Are you looking for ConnectedComponents? $\endgroup$
    – Daniel Lichtblau
    Commented May 29, 2015 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
    Commented May 29, 2015 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
    Commented May 29, 2015 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
    Commented Jun 15, 2015 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
    Commented Jun 15, 2015 at 15:46

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ With that being said, one might care about output-sensitive algorithms, see here. $\endgroup$
    – Juho
    Commented Jun 18, 2015 at 12:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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