# Complexity of counting all connected subgraphs

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!

• Are you aware that the list in the question is not formatted correctly? meta.cstheory.stackexchange.com/questions/300/… 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 Dec 2 '10 at 16:00
• 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 Dec 2 '10 at 16:21
• 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 Dec 2 '10 at 19:11
• 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 Dec 2 '10 at 19:30
• This paper isn't exactly what you asked for, but the paper and its references may help in developing some ideas. – M.S. Dousti Feb 20 '11 at 8:32

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 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?

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.

• 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 Feb 21 '11 at 1:38