<p>Welsh states that the problem #P-complete even in the most restricted case (counting the number of connected subgraphs of a planar bipartite graph). See the bottom of <a href="http://books.google.com/books?id=pe3CJmT_EOYC&amp;pg=PA305&amp;dq=%22number+of+connected+subgraphs%22+%22%23p-complete%22&amp;hl=en&amp;ei=tG9hTdzWHInYgQeTnJSpAg&amp;sa=X&amp;oi=book_result&amp;ct=result&amp;resnum=1&amp;ved=0CCcQ6AEwAA#v=onepage&amp;q=%22number%20of%20connected%20subgraphs%22%20%22%23p-complete%22&amp;f=false" rel="nofollow">page 305</a> in Welsh, Dominic (1997), "Approximate Counting", <em>Surveys in Combinatorics</em>, Bailey, R. A., ed., Cambridge University Press, pp. 287–324.</p>

<p>In context, though, I wonder whether he really means connected spanning subgraphs. And that leads me to wonder which version of the problem you want: connected spanning subgraphs, connected subgraphs that need not be spanning, or connected induced subgraphs?</p>

CC BY-SA 2.5
2011-02-20T19:51:39.987Z
2011-02-20T20:06:58.540Z
2011-02-20T20:06:58.540Z
David Eppstein
<p>This is a response to David's answer. Without having looked at that book yet I'd guess the problem is counting connected spanning subgraphs, because this is the point x=1 y=2 of the Tutte polynomial, and the author was interested in that. But in fact I think those three problems reduce quite easily from counting connected spanning subgraph problem. The following reductions should work for either exact counting or approximation, though I think the problem for approximation is still open.</p>

<p>Counting connected spanning subgraphs reduces to counting connected subgraphs (sketch): 
Take a graph G in which we wish to count spanning subgraphs. Attach a $K_A$ to each vertex. If $A$ is chosen large enough, typical connected subgraphs of the resulting graph correspond N-to-1 to connected spanning subgraphs in G, where N is easy to compute.</p>

<p>Counting connected spanning subgraphs reduces to counting connected induced subgraphs (sketch):
Let G be a graph in which we wish to count spanning subgraphs. Divide each edge in two, so there are now |V|+|E| vertices. Attach a $K_A$ to each of the original vertices that were in G. If $A$ is chosen large enough, typical connected induced subgraphs of the resulting graph correspond N-to-1 to connected spanning subgraphs in G, where N is easy to compute.</p>

<p>Here's another interpretation of the question: what about counting unlabelled connected subgraphs? This is $\#P$ hard even for trees: L.A. Goldberg and M. Jerrum, Counting unlabelled subtrees of a tree is #P-Complete, LMS Journal of Computation and Mathematics, 3 (2000) 117-124.</p>

CC BY-SA 2.5
2011-02-21T01:38:03.530Z
You don't need to attach a clique, right? You could attach anything that has a lot of connected subgraphs, as long as you attach the same thing to each vertex. So you could do these reductions while preserving both planarity and bipartiteness.
David Eppstein
CC BY-SA 2.5
2011-02-20T22:40:54.037Z
2011-02-20T22:40:54.037Z
Colin McQuillan
<p>Let G be a connected graph.</p>

<blockquote>
  <p>What is the complexity of counting all <em>connected subgraphs</em> if G is of the following types?</p>
  
  <ul>
  <li>G is general.</li>
  <li>G is planar.</li>
  <li>G is bipartite.</li>
  </ul>
</blockquote>

<p>I don't care about any structures or ..., just need to count all the connected subgraphs!
I'm also interested in the complexity of counting all connected subgraphs <em>with exactly k nodes</em> in G.</p>

<p>Pointers to papers and books are also welcomed!</p>

CC BY-SA 2.5
2010-12-02T16:00:11.977Z
Are you aware that the list in the question is not formatted correctly?  http://meta.cstheory.stackexchange.com/questions/300/how-to-ask-a-good-question/328#328  If you do not care about formatting, that is fine.  But I am not sure if anyone wants to spend time to answer your question when you do not want to spend time to format your question properly.  (I am not saying that I know the answer.)
Tsuyoshi Ito
CC BY-SA 2.5
2010-12-02T16:21:00.187Z
Also, do you care about enumerating connected subgraphs of arbitrary size/order/structure/..., or do you wish them to be spanning, or anything else?
Anthony Labarre
CC BY-SA 2.5
2010-12-02T19:11:16.067Z
There seems to work on counting connected *spanning* subgraphs. Page 32 of Sokal's "multivariate Tutte Polynomial" connects spanning subgraph polynomial to reliability polynomial which has a huge literature
Yaroslav Bulatov
CC BY-SA 2.5
2010-12-02T19:30:27.340Z
I'm sorry, my previous answer on using Kirchhoff's theorem was wrong. I thought about an inclusion-exclusion argument but this might be infeasible.
didest
CC BY-SA 2.5
2011-02-20T08:32:11.493Z
[This paper](http://dx.doi.org/10.1093/ietfec/e91-a.9.2314) isn't exactly what you asked for, but the paper and [its references](http://www.jstage.jst.go.jp/article/transfun/E91.A/9/E91.A_2314/_cit) may help in developing some ideas.
Sadeq Dousti
<cc.complexity-theory><graph-theory><counting-complexity>
Complexity of counting all connected subgraphs
marjoonjan
# Complexity of counting all connected subgraphs

(Asked by: username_0 on 2010-12-02)

Let G be a connected graph.

> What is the complexity of counting all *connected subgraphs* if G is of the following types?
>
> * G is general.
> * G is planar.
> * G is bipartite.

I don't care about any structures or ..., just need to count all the connected subgraphs!
I'm also interested in the complexity of counting all connected subgraphs *with exactly k nodes* in G.

Pointers to papers and books are also welcomed!

**Tags:** cc.complexity-theory, graph-theory, counting-complexity
> **Comments:**
> **username_1**: Are you aware that the list in the question is not formatted correctly?  http://meta.cstheory.stackexchange.com/questions/300/how-to-ask-a-good-question/328#328  If you do not care about formatting, that is fine.  But I am not sure if anyone wants to spend time to answer your question when you do not want to spend time to format your question properly.  (I am not saying that I know the answer.)  
> **username_2**: Also, do you care about enumerating connected subgraphs of arbitrary size/order/structure/..., or do you wish them to be spanning, or anything else?  
> **username_3**: There seems to work on counting connected *spanning* subgraphs. Page 32 of Sokal's "multivariate Tutte Polynomial" connects spanning subgraph polynomial to reliability polynomial which has a huge literature  
> **username_4**: I'm sorry, my previous answer on using Kirchhoff's theorem was wrong. I thought about an inclusion-exclusion argument but this might be infeasible.  
> **username_5**: [This paper](http://dx.doi.org/10.1093/ietfec/e91-a.9.2314) isn't exactly what you asked for, but the paper and [its references](http://www.jstage.jst.go.jp/article/transfun/E91.A/9/E91.A_2314/_cit) may help in developing some ideas.  

---

## 2 answers

### Answer by username_6 on 2011-02-20. Score: 14

Welsh states that the problem #P-complete even in the most restricted case (counting the number of connected subgraphs of a planar bipartite graph). See the bottom of [page 305](http://books.google.com/books?id=pe3CJmT_EOYC&pg=PA305&dq=%22number+of+connected+subgraphs%22+%22%23p-complete%22&hl=en&ei=tG9hTdzWHInYgQeTnJSpAg&sa=X&oi=book_result&ct=result&resnum=1&ved=0CCcQ6AEwAA#v=onepage&q=%22number%20of%20connected%20subgraphs%22%20%22%23p-complete%22&f=false) in Welsh, Dominic (1997), "Approximate Counting", *Surveys in Combinatorics*, Bailey, R. A., ed., Cambridge University Press, pp. 287–324.

In context, though, I wonder whether he really means connected spanning subgraphs. And that leads me to wonder which version of the problem you want: connected spanning subgraphs, connected subgraphs that need not be spanning, or connected induced subgraphs?


---

### Answer by username_7 on 2011-02-20. Score: 6

This is a response to David's answer. Without having looked at that book yet I'd guess the problem is counting connected spanning subgraphs, because this is the point x=1 y=2 of the Tutte polynomial, and the author was interested in that. But in fact I think those three problems reduce quite easily from counting connected spanning subgraph problem. The following reductions should work for either exact counting or approximation, though I think the problem for approximation is still open.

Counting connected spanning subgraphs reduces to counting connected subgraphs (sketch):
Take a graph G in which we wish to count spanning subgraphs. Attach a $K\_A$ to each vertex. If $A$ is chosen large enough, typical connected subgraphs of the resulting graph correspond N-to-1 to connected spanning subgraphs in G, where N is easy to compute.

Counting connected spanning subgraphs reduces to counting connected induced subgraphs (sketch):
Let G be a graph in which we wish to count spanning subgraphs. Divide each edge in two, so there are now |V|+|E| vertices. Attach a $K\_A$ to each of the original vertices that were in G. If $A$ is chosen large enough, typical connected induced subgraphs of the resulting graph correspond N-to-1 to connected spanning subgraphs in G, where N is easy to compute.

Here's another interpretation of the question: what about counting unlabelled connected subgraphs? This is $\#P$ hard even for trees: L.A. Goldberg and M. Jerrum, Counting unlabelled subtrees of a tree is #P-Complete, LMS Journal of Computation and Mathematics, 3 (2000) 117-124.

> **Comments:**
> **username_6**: You don't need to attach a clique, right? You could attach anything that has a lot of connected subgraphs, as long as you attach the same thing to each vertex. So you could do these reductions while preserving both planarity and bipartiteness.  

---

