19
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Sergey, I tried to edit your question to improve clarity. Please check that I understood your question correctly and did not introduce any errors. $\endgroup$ – Tyson Williams Apr 27 '13 at 21:35
  • 1
    $\begingroup$ 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)$. $\endgroup$ – Finsky Apr 29 '13 at 15:28
  • $\begingroup$ For more information on Cayley graphs see this book. $\endgroup$ – Finsky Apr 29 '13 at 15:30
  • 1
    $\begingroup$ Doing Linear algebra with the Laplacian rather than a general matrix is often easier. I wonder if this can be relevant. $\endgroup$ – Gil Kalai May 1 '13 at 16:25
  • $\begingroup$ 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. $\endgroup$ – Finsky May 2 '13 at 15:22
12
+50
$\begingroup$

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

$\endgroup$

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.