<p>It is <a href="http://bura.brunel.ac.uk/bitstream/2438/817/1/tutte.pdf">known</a> that, for $G$ of bounded treewidth, the Tutte polynomial $T(G;x,y)$ can be evaluated at any $(x,y)$ using $O(n)$ arithmetic operations. If $G$ is connected, then $t(G)=T(G;1,1)$.</p>

CC BY-SA 3.0
2013-04-30T16:02:31.970Z
2013-04-30T16:02:31.970Z
Radu Curticapean
<p>Let $t(G)$ denote the number of spanning trees in a graph $G$ with $n$ vertices.  There is an algorithm that computes $t(G)$ in $O(n^3)$ arithmetic operations. This algorithm is to compute $\frac{1}{n^2} \det(J + Q)$, where $Q$ is the Laplacian of of $G$ and $J$ is the matrix consisting solely of $1$'s. For more information on this algorithm see <a href="http://rads.stackoverflow.com/amzn/click/0521458978" rel="nofollow noreferrer">Biggs - Algebraic graph theory</a> or <a href="https://math.stackexchange.com/questions/90950/finding-the-number-of-spanning-trees-of-a-graph-g">this Math SE</a> question.</p>

<p>I wonder if there is some way to compute $t(G)$ faster. (Yes, there is faster than $O(n^3)$ algorithms for computing determinant but I am interested in some new approach.)</p>

<p>It's also interested in considering special families of graphs (planar, maybe?).</p>

<p>For example, for circulant graphs, $t(G)$ can be computed in $O(n \lg n)$ arithmetic operations via the identity $t(G) = \frac{1}{n} \lambda_1 \dotsm \lambda_{n-1}$, where $\lambda_i$ are nonzero eigenvalues of Laplacian matrix of $G$, which can be computed quickly for circulant graphs. (Represent the first row as a polynomial and then compute it on $n$-th roots of unity - this step uses the Discrete Fourier transformation and can be done in $O(n \lg n)$ arithmetic operations.)</p>

<p>Thank you very much!</p>

CC BY-SA 3.0
2013-04-27T21:35:08.623Z
Sergey, I tried to edit your question to improve clarity.  Please check that I understood your question correctly and did not introduce any errors.
Tyson Williams
CC BY-SA 3.0
2013-04-29T15:28:50.197Z
Here is one more general example of graph families where finding complexity can be done faster: Cayley graphs for abelian groups $G$ with generators set $S$, such that $S^{-1} = S$. We know that eigenvalues of such matrix are $\sum_{h \in S} \chi (h)$, where $\chi$ are different characters of the group. All characters are easy to find (for more information consult [this paper](http://www.math.uconn.edu/~kconrad/blurbs/grouptheory/charthy.pdf)) computing those characters is $n$-dimensional FFT (see Cormen et al chapter on FFT), i.e. can be done in $O(n \lg n)$.
user197284
CC BY-SA 3.0
2013-04-29T15:30:09.093Z
For more information on Cayley graphs see [this book](http://www.win.tue.nl/~aeb/2WF02/spectra.pdf).
user197284
CC BY-SA 3.0
2013-05-01T16:25:09.867Z
Doing Linear algebra with the Laplacian rather than a general matrix is often easier. I wonder if this can be relevant.
Gil Kalai
CC BY-SA 3.0
2013-05-02T15:22:22.207Z
Could you, please, be more specific, if it possible, provide some examples, even if it's not directly related to the topic in discussion. Thank you.
user197284
<graph-theory><graph-algorithms><counting-complexity><spectral-graph-theory>
Count the number of spanning trees fast
user197284
# Count the number of spanning trees fast

(Asked by: username_0 on 2013-04-27)

Let $t(G)$ denote the number of spanning trees in a graph $G$ with $n$ vertices. There is an algorithm that computes $t(G)$ in $O(n^3)$ arithmetic operations. This algorithm is to compute $\frac{1}{n^2} \det(J + Q)$, where $Q$ is the Laplacian of of $G$ and $J$ is the matrix consisting solely of $1$'s. For more information on this algorithm see [Biggs - Algebraic graph theory](http://rads.stackoverflow.com/amzn/click/0521458978) or [this Math SE](https://math.stackexchange.com/questions/90950/finding-the-number-of-spanning-trees-of-a-graph-g) question.

I wonder if there is some way to compute $t(G)$ faster. (Yes, there is faster than $O(n^3)$ algorithms for computing determinant but I am interested in some new approach.)

It's also interested in considering special families of graphs (planar, maybe?).

For example, for circulant graphs, $t(G)$ can be computed in $O(n \lg n)$ arithmetic operations via the identity $t(G) = \frac{1}{n} \lambda\_1 \dotsm \lambda\_{n-1}$, where $\lambda\_i$ are nonzero eigenvalues of Laplacian matrix of $G$, which can be computed quickly for circulant graphs. (Represent the first row as a polynomial and then compute it on $n$-th roots of unity - this step uses the Discrete Fourier transformation and can be done in $O(n \lg n)$ arithmetic operations.)

Thank you very much!

**Tags:** graph-theory, graph-algorithms, counting-complexity, spectral-graph-theory
> **Comments:**
> **username_1**: Sergey, I tried to edit your question to improve clarity.  Please check that I understood your question correctly and did not introduce any errors.  
> **username_0**: Here is one more general example of graph families where finding complexity can be done faster: Cayley graphs for abelian groups $G$ with generators set $S$, such that $S^{-1} = S$. We know that eigenvalues of such matrix are $\sum_{h \in S} \chi (h)$, where $\chi$ are different characters of the group. All characters are easy to find (for more information consult [this paper](http://www.math.uconn.edu/~kconrad/blurbs/grouptheory/charthy.pdf)) computing those characters is $n$-dimensional FFT (see Cormen et al chapter on FFT), i.e. can be done in $O(n \lg n)$.  
> **username_0**: For more information on Cayley graphs see [this book](http://www.win.tue.nl/~aeb/2WF02/spectra.pdf).  
> **username_2**: Doing Linear algebra with the Laplacian rather than a general matrix is often easier. I wonder if this can be relevant.  
> **username_0**: Could you, please, be more specific, if it possible, provide some examples, even if it's not directly related to the topic in discussion. Thank you.  

---

## 1 answers

### Answer by username_3 on 2013-04-30. Score: 13

It is [known](http://bura.brunel.ac.uk/bitstream/2438/817/1/tutte.pdf) that, for $G$ of bounded treewidth, the Tutte polynomial $T(G;x,y)$ can be evaluated at any $(x,y)$ using $O(n)$ arithmetic operations. If $G$ is connected, then $t(G)=T(G;1,1)$.


---

