Approximate Spanning Tree Counting from Uncorrelated Edge Sets

Yang P. Liu, Richard Peng, Junzhao Yang

We show an $\tilde{O}(m^{1.5}{\epsilon }^{-1})$ time algorithm that on a graph with $m$ edges and $n$ vertices outputs its spanning tree count up to a multiplicative $(1+\epsilon )$ factor with…