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

<ol>
<li>$\ge 1$ cycle each (but can have any number of cycles),</li>
<li>Exactly $k \ge 1$ cycles each.</li>
</ol>

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

<p>For the first case, it seems that we can just count the number of connected subgraphs (<a href="https://cstheory.stackexchange.com/questions/3465/complexity-of-counting-all-connected-subgraphs">which seems to be #P-complete</a>), 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.</p>

<p>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$.</p>

<p>The application of this would be on better approximating coefficients of the reliability polynomial.</p>

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

<p><strong>Edit 2</strong>: for planar graphs, counting unicyclic subgraphs is poly-time computable (and due to Myrvold, this is reducible to matrix multiplication): <a href="http://link.springer.com/article/10.1007%2FBF01994058" rel="nofollow noreferrer">http://link.springer.com/article/10.1007%2FBF01994058</a></p>

CC BY-SA 3.0
2015-11-22T00:23:15.950Z
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.
Sasho Nikolov
CC BY-SA 3.0
2015-11-22T00:27:28.443Z
@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.
Ryan Dougherty
CC BY-SA 3.0
2015-11-22T00:59:21.663Z
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$.
Sasho Nikolov
CC BY-SA 3.0
2016-07-10T18:22:42.220Z
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 http://arxiv.org/pdf/1402.4169v2.pdf. See the latter article for another application of counting spanning unicyclic graphs to computing densities of abelian sandpiles.
Sasho Nikolov
CC BY-SA 3.0
2016-07-11T15:46:15.300Z
@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!
Ryan Dougherty
<graph-theory><counting-complexity>
Complexity of counting spanning subgraphs that have cycle properties
Ryan Dougherty
# Complexity of counting spanning subgraphs that have cycle properties

(Asked by: username_0 on 2015-11-05)

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](https://cstheory.stackexchange.com/questions/3465/complexity-of-counting-all-connected-subgraphs)), 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>

**Tags:** graph-theory, counting-complexity

> **Comments:**
> **username_1**: 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.  
> **username_0**: @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.  
> **username_1**: 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$.  
> **username_1**: 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 http://arxiv.org/pdf/1402.4169v2.pdf. See the latter article for another application of counting spanning unicyclic graphs to computing densities of abelian sandpiles.  
> **username_0**: @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!  

---

## 0 answers

