12
$\begingroup$

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!

Improve this question
$\endgroup$
5
  • 4
    $\begingroup$ 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.) $\endgroup$
    – Tsuyoshi Ito
    Dec 2, 2010 at 16:00
  • $\begingroup$ Also, do you care about enumerating connected subgraphs of arbitrary size/order/structure/..., or do you wish them to be spanning, or anything else? $\endgroup$
    – Anthony Labarre
    Dec 2, 2010 at 16:21
  • 2
    $\begingroup$ 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 $\endgroup$
    – Yaroslav Bulatov
    Dec 2, 2010 at 19:11
  • $\begingroup$ 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. $\endgroup$
    – didest
    Dec 2, 2010 at 19:30
  • 1
    $\begingroup$ This paper isn't exactly what you asked for, but the paper and its references may help in developing some ideas. $\endgroup$
    – Sadeq Dousti
    Feb 20, 2011 at 8:32

2 Answers 2

Reset to default
14
$\begingroup$

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?

Improve this answer
$\endgroup$
6
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$
    – David Eppstein
    Feb 21, 2011 at 1:38

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.