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!

$\endgroup$
  • 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 '10 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 '10 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 '10 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$ – Diego de Estrada Dec 2 '10 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$ – M.S. Dousti Feb 20 '11 at 8:32
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?

$\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.

$\endgroup$
  • 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 '11 at 1:38

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.