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!

Improve this question
$\endgroup$
5
  • $\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, 2013 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$
    – user197284
    Apr 29, 2013 at 15:28
  • $\begingroup$ For more information on Cayley graphs see this book. $\endgroup$
    – user197284
    Apr 29, 2013 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, 2013 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$
    – user197284
    May 2, 2013 at 15:22

1 Answer 1

Reset to default
13
+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)$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.