Conte o número de árvores abrangidas rapidamente

Seja o número de árvores que se estendem em um gráfico com vértices. Existe um algoritmo que calcula em operações aritméticas . Este algoritmo é computado , onde Q é o Laplaciano de G e J é a matriz que consiste apenas em 1 's. Para obter mais informações sobre esse algoritmo, consulte Biggs - Teoria dos grafos algébricos ou esta questão da matemática SE .G n t ( G ) O ( n 3 ) $t(G)$$G$$n$$t(G)$$O(n^3)$QGJ$\frac{1}{n^2} \det(J + Q)$$Q$$G$$J$$1$

Gostaria de saber se existe alguma maneira de calcular $t(G)$ mais rapidamente. (Sim, existem algoritmos mais rápidos que $O(n^3)$ para determinantes da computação, mas estou interessado em alguma nova abordagem.)

Também está interessado em considerar famílias especiais de gráficos (planares, talvez?).

Por exemplo, para gráficos circulantes, $t(G)$ pode ser computado em operações aritméticas $O(n \lg n)$ através da identidade $t(G) = \frac{1}{n} \lambda_1 \dotsm \lambda_{n-1}$ , onde $\lambda_i$ são autovalores diferentes de zero da matriz laplaciana de $G$ , que podem ser calculados rapidamente para gráficos circulantes. (Represente a primeira linha como um polinômio e depois calcule-a na $n$ ésima raiz da unidade - esta etapa usa a transformação Discrete Fourier e pode ser feita em operações aritméticas $O(n \lg n)$ .)

Muito obrigado!

É conhecido que, para de treewidth limitada, o Tutte polinomial pode ser avaliado em qualquer utilizando as operações aritméticas. Se estiver conectado, então .$G$$T(G;x,y)$$(x,y)$$O(n)$$G$$t(G)=T(G;1,1)$