An $m+n^{3/2}$ algorithm for counting spanning trees by ${\ell }_1$-regularized resistance

Abstract

We study the basic problem of approximating the number of spanning trees of a graph. For a graph with $n$ vertices, $m$ edges, We propose an algorithm that approximates the number of spanning trees in $\widetilde O(m+n^{3/2}\eps^{-1})$ time. 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^{3/2}\eps^{-1})$ time algorithm by Liu, Peng, and Yang [FOCS 2026]. Notably, our algorithm is based on the novel concept of ${\ell }_1$-regularized resistance. We propose simple and efficient algorithm 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]. Our algorithm matches the best known size of the determinant sparsifiers.