2
$\begingroup$

Let $G = (V, E)$ be a connected undirected graph. I am interesting in counting the number of connected spanning subgraphs having:

  1. $\ge 1$ cycle each (but can have any number of cycles),
  2. Exactly $k \ge 1$ cycles each.

The subgraphs that have $k=1$ are called unicyclic subgraphs. So essentially, I want to count the number of unicyclic spanning subgraphs.

For the first case, it seems that we can just count the number of connected subgraphs (which seems to be #P-complete), then use Kirchhoff's matrix tree theorem to find the number of spanning trees, and find the difference of the two to get the number of connected subgraphs with $\ge 1$ cycle each.

The second problem seems like a special case of the first, but I haven't been able to find any resources of its complexity. I'm not even sure how to do this for a fixed value of $k$.

The application of this would be on better approximating coefficients of the reliability polynomial.

Edit: another interesting direction would be to investigate $k$-regular graphs for $k \ge 3$ (the $k=2$ case is known, of course).

Edit 2: for planar graphs, counting unicyclic subgraphs is poly-time computable (and due to Myrvold, this is reducible to matrix multiplication): http://link.springer.com/article/10.1007%2FBF01994058

$\endgroup$
  • $\begingroup$ Are you interested in approximate results? There is a simple rejection sampling algorithm (that I learned from Yuval Peres) for sampling connected subgraphs with $n$ edges (i.e. with a unique cycle): sample a uniform spanning tree $T$, sample a uniform edge $e$ in $G-T$, and let $L$ be the length of the unique cycle in $T + e$; with probability $1/L$ output $T+e$ and with the remaining probability reject and repeat the process. By the equivalence of sampling and approximate counting, this gives a randomized procedure to approximate the number of $n$-edge spanning subgraphs. $\endgroup$ – Sasho Nikolov Nov 22 '15 at 0:23
  • $\begingroup$ @SashoNikolov thank you! Do you have a link/reference of where that came from? I would prefer exact results but approximate ones are useful also. $\endgroup$ – Ryan Nov 22 '15 at 0:27
  • $\begingroup$ No link, this came up in a conversation. Also it's relatively straightforward, so I would consider it folklore. The non-trivial parts to the argument are 1) a uniform spanning tree can be generated efficiently (there are many algorithms for this, some based on random walks, and some based on the matrix tree theorem), and 2) the equivalence between sampling and approximate counting, which is covered in many books and lecture notes. I believe you can generalize to uniformly sampling a graph with $n+k$ edges for any constant $k$. $\endgroup$ – Sasho Nikolov Nov 22 '15 at 0:59
  • $\begingroup$ Myrvold's article (which has a much simpler proof of the planar graph result) suggests that your problem is open for general graphs. The article is from 1992, but this newer one (from 2016) suggests this is still the case arxiv.org/pdf/1402.4169v2.pdf. See the latter article for another application of counting spanning unicyclic graphs to computing densities of abelian sandpiles. $\endgroup$ – Sasho Nikolov Jul 10 '16 at 18:22
  • $\begingroup$ @SashoNikolov thanks! I knew that it was open from Myrvold, but couldn't find a reference for its being open since then. I guess that it is still open! $\endgroup$ – Ryan Jul 11 '16 at 15:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.