2
$\begingroup$

For a given undirected graph G, I want to count all the subgraphs H that satisfies the following conditions:

  • H.V = G.V (The subgraph will containt all the original graph nodes)
  • H is connected

(Note: I don't care if two subgraphs are isomorphic)

The graphs which I will be working with will have |G.V| <= 15

Improve this question
$\endgroup$
7
  • 3
    $\begingroup$ Are you interested in the number of nonisomorphic graphs or the total of all (connected) subgraphs? In either case, you could help us to help you by describing what you've tried so far. $\endgroup$
    – Rick Decker
    Jun 7 '16 at 13:57
  • 2
    $\begingroup$ What do you mean by "H.V" and "G.V"? $\endgroup$
    – David Richerby
    Jun 7 '16 at 15:21
  • 1
    $\begingroup$ By H.V do you mean the vertices of H? $\endgroup$
    – Michael Klein
    Jun 7 '16 at 17:42
  • $\begingroup$ The subgraph will containt all the original graph nodes $\endgroup$
    – Naif
    Jun 7 '16 at 18:34
  • 2
    $\begingroup$ Still it would be nice to answer to comments by editing the question. $\endgroup$
    – Evil
    Jun 7 '16 at 18:38
4
$\begingroup$

Your problem is known as counting the number of connected spanning subgraphs, and is pretty hard even for restricted classes of graphs. See this question on cstheory.

The number of connected spanning subgraphs of a graph $G$ equals $T_G(1,2)$, where $T_G$ is the Tutte polynomial of $G$ (this is mentioned in one of the answers to the linked question). Hence this paper of Björklund et al., which shows how to compute said polynomial in vertex-exponential time (i.e., $\exp O(n)$), gives us hope, since in your case $n$ is pretty small ($n \leq 15$).

Improve this answer
$\endgroup$

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.