Improved algorithm for counting spanning trees by $\ell_1$-regularized resistance
TL;DR
This work proposes an algorithm that approximates the number of spanning trees in $\widetilde O(m+n^{7/4}\eps^{-3/2})$ time on a graph with $n$ vertices and $m$ edges and is based on the novel concept of $\ell_1$-regularized resistance.
Abstract
We study the basic problem of approximating the number of spanning trees of a graph. We propose an algorithm that approximates the number of spanning trees in $\widetilde O(m+n^{7/4}\eps^{-3/2})$ time on a graph with $n$ vertices and $m$ edges. Our algorithm improves upon the previously best known $\widetilde O(m+n^{15/8}\eps^{-7/4})$ time algorithm by Chu, Gao, Peng, Sachdeva, Sawlani, and Wang [FOCS 2018] and the $\widetilde O(m^{1.5}\eps^{-1})$ time algorithm by Liu, Peng and Yang [FOCS 2026] when $m\ge n^{7/6}$. Notably, our algorithm is based on the novel concept of $\ell_1$-regularized resistance. We propose simple and efficient algorithms for computing $\ell_1$-regularized resistance and we show that they can be used to approximate the number of spanning trees by combining with the determinant sparsifier framework of Durfee, Peebles, Peng, and Rao [FOCS 2017].
