19

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 or this Math SE 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!

Community
  • 1
user197284
  • 605
  • 3
  • 11
  • 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 Apr 27 '13 at 21:35
  • 1
    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) 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 Apr 29 '13 at 15:28
  • For more information on Cayley graphs see this book. – user197284 Apr 29 '13 at 15:30
  • 1
    Doing Linear algebra with the Laplacian rather than a general matrix is often easier. I wonder if this can be relevant. – Gil Kalai May 01 '13 at 16:25
  • 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 May 02 '13 at 15:22

1 Answers1

13

It is known 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)$.

Radu Curticapean
  • 817
  • 6
  • 12