Approximate Spanning Tree Counting from Uncorrelated Edge Sets

Junzhao Yang; Richard Peng; Yang P. Liu

REVIEW 2 major objections 5 minor 19 references

Approximate Spanning Tree Counting from Uncorrelated Edge Sets

T0 review · 2 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper gives an O~(m^1.5 epsilon^-1) time algorithm for approximate spanning tree counting using recursive deletion of uncorrelated edge sets found via electrical-flow localization.

desk verdict A real runtime improvement and a genuinely new algorithmic idea, with a missing connectivity argument that is fixable and likely true. read the letter →

arxiv 2505.14666 v1 pith:THIFGL3Z submitted 2025-05-20 cs.DS

Yang P. Liu , Richard Peng , Junzhao Yang This is my paper · ORCID

classification cs.DS

keywords epsilonalgorithmedgesprevioussetsspanningtreeuncorrelated

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Counting spanning trees is a classic graph problem: given a network, how many different ways can you choose edges so that every node stays connected with no cycles? The exact count is a huge number, so algorithms often try to approximate it within a small percentage. The new paper shows a faster randomized way to do this. The method starts from an older observation: the chance that a particular edge belongs to a random spanning tree can be computed from electrical flows through the graph. If you pick a set of edges that are almost independent, the spanning tree count of the graph changes in a predictable way when those edges are deleted. The authors find such sets using a theorem about electrical flow localization: on average, electrical flows stay near their source and destination, so most pairs of edges barely interact. The algorithm repeatedly finds a batch of these uncorrelated edges, estimates how much the spanning tree count changes when they are removed, deletes them, and repeats until the graph is small. The total work is about m to the power 1.5 divided by epsilon, where m is the number of edges and epsilon is the allowed error. For sparse graphs this beats the previous best algorithm, which took time closer to n to the power 1.875. The proof combines matrix tree theorem, Laplacian solvers, and randomized sketching. The main caveat is that the recursion implicitly assumes the graph stays connected after each deletion, which the paper does not explicitly prove.

Extended reading notes

Core claim

Theorem 1 states that there is a routine ApproxSpanningTree(G, epsilon) that, for an undirected graph with n vertices, m edges, and polynomially bounded weights, outputs in O~(m^1.5 epsilon^-1) time a (1+epsilon) multiplicative approximation of the spanning tree count with high probability. If correct, this improves the previous best sparse-graph runtime from O~(m + n^1.875 epsilon^-7/4).

Load-bearing premise

After each recursive deletion step, the graph (V, E\F, w) remains connected, so that the spanning tree count and the Laplacian determinant are well-defined. The paper never states or proves this, and it is not an immediate consequence of the stated uncorrelated-edge conditions; the algorithm in Figure 1 step 6 recurses on (V, E\F, w) without addressing possible disconnection.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The paper deserves a serious referee, and I expect a conditional accept after a small revision. The core result is real: an O~(m^1.5 eps^{-1}) algorithm for (1+eps)-approximating the spanning tree count, beating the previous O~(m + n^1.875) for sparse graphs. The approach is genuinely different from the Schur-complement/determinantal-sparsification line: it repeatedly finds a small 'uncorrelated' edge set via electrical flow localization, deletes it, and recurses. That's a nice idea and the high-level structure is sound.

The main gap is exactly what the stress-test flags: the recursion assumes G\F remains connected, and the paper never says why. The determinant identity in Section 3 and Lemma 5.2 require a connected graph; for a disconnected G\F, T(G\F)=0 and the logarithm breaks. That said, the missing invariant is true and short to prove. For a cut C, sum_{e in C} tau_e = 1, and for any two cut edges e,f, |M_{e,f}| = sqrt(tau_e tau_f). If F is rho-uncorrelated with rho<0.4 and every tau_e <=0.8, then taking the edge f* with maximum tau (0.8) gives Cor(f*, C\{f*}) >= sqrt(0.8)*sqrt(0.2) = 0.4, a contradiction. So no such F can contain a cut. The authors just need to add this lemma. It is a gap in exposition, not a hole in the result.

Other issues are minor. Lemma 4.3 says 'at least 1.9k edges are kept' but the previous line gives at most 0.1|F+| = 0.2k discarded, so 1.8k. Just a typo. The pseudocode in Figure 1 has no base case; the text should say what happens when m is small. The phase-level variance bound is compressed but the calculation checks out: per-iteration bias/variance O(k_i^3/m_i^2 log^4), times m_i/k_i iterations gives O(eps^2/log^2) per phase, summing to O(eps^2).

The literature use is fair; the self-citations are to background tools, not to the central claim. The proof is not circular.

Bottom line: read it as a solid FOCS/SODA-style paper that needs a small revision. The connectivity lemma is the one thing a referee must insist on; everything else is cosmetic. Send it to peer review.

Referee Report

2 major / 5 minor

Summary. The paper presents an algorithm ApproxSpanningTree that approximates the spanning tree weight of an undirected weighted graph by repeatedly deleting sets of "uncorrelated" edges. For a graph with m edges, n vertices, and polynomially bounded weights, it claims a (1+epsilon) multiplicative approximation in O~(m^{1.5} epsilon^{-1}) time, improving on the previous O~(m + n^{1.875} epsilon^{-7/4}) bound for sparse graphs. The main technical machinery is a determinant identity relating log T(G\F) - log T(G) to a log-determinant of an |F|-by-|F| matrix whose off-diagonal entries are small for uncorrelated edge sets; such sets are found using the electrical flow localization theorem of Schild-Rao-Srivastava and standard leverage-score estimation. The paper gives detailed lemmas for estimating leverage scores, estimating weighted sums of leverage scores, and finding uncorrelated edge subsets, followed by a recursive algorithm and a phase-based variance analysis.

Significance. If correct, this is a notable improvement for sparse graphs and introduces a genuinely different approach to Laplacian determinant estimation. The proof is largely self-contained and builds on standard external tools (Laplacian solvers, leverage-score sketching, and l1-stable sketches), and the central claim is not circular: each estimator is derived from first principles, not from the theorem being proved. The main weaknesses are an unstated connectivity invariant for the recursive deletion step and a parameter regime (very small epsilon) that is not covered as written; both appear repairable, but they are load-bearing for the proof as presented.

major comments (2)

[§5, Figure 1 / Lemma 5.2] The recurrence uses log T(G\F), which is only defined when G\F is connected, but the manuscript never states or proves that the deleted edge set F cannot disconnect G. This is load-bearing: if F contained all edges of a cut, the determinant identity of Section 3 would give det^+(L(G\F)) = 0, so log T(G\F) would be undefined and the recurrence would not approximate the spanning tree count. The gap is repairable: under the hypotheses of Lemma 5.2, the matrix A with entries A_{e,f} = w_e^{1/2} b(e)^T L(G)^† b(f) w_f^{1/2} has diagonal entries at most 0.88 and off-diagonal row sums at most rho <= 0.01, so ||A||_2 <= 0.89, det(I-A) > 0, and hence det^+(L(G\F)) > 0; for a Laplacian this positivity is equivalent to G\F being connected. Please insert this invariant explicitly before Lemma 5.2 and use it inductively in the proof of Theorem 1.
[§5, Theorem 1] The theorem is stated for all 0 < epsilon < 1, but the algorithm in Figure 1 has no base case and calls GetUncorrelated with k = Theta(epsilon sqrt(m) / (log m)^3). For epsilon smaller than about (log m)^3 / sqrt(m), this k is less than 1, so Lemma 4.3 cannot be applied as stated. Additionally, Lemma 5.1 can reduce a connected graph to an empty graph, and the recursion needs a stopping rule. These issues are local but must be fixed for the theorem to hold in the stated range, for example by using exact determinant computation when epsilon is below a threshold (noting that the runtime is then within the claimed bound) or by defining k = max(1, Theta(epsilon sqrt(m)/(log m)^3)) and rederiving the error bound in the k = 1 regime.

minor comments (5)

[§4.3, Lemma 4.3] In the proof, after two Markov inequalities the algorithm keeps at least 1.8k edges, not 1.9k (at most 0.1|F+| = 0.2k edges are discarded); the conclusion is unaffected because 1.8k >= k, but the number should be corrected.
[§4.2, Lemma 4.2] The displayed chain ending in "= 2|F|rho^2" should be "<= 2|F|rho^2", and the proof uses theta_e <= 1 to drop the theta_e theta_f factors; please state explicitly that the lemma requires theta in [0,1]^F.
[§4.3, Lemma 4.3] The lemma is stated as succeeding with high probability, but the proof only establishes a constant probability that at least k edges survive; please add the standard repetition argument (O(log n) independent trials) that upgrades the success probability.
[§5, Figure 1] The recursion has no stated base case: when Lemma 5.1 reduces the graph to an empty graph or to a graph with no edges, steps 2-5 are undefined. Specify a stopping rule, e.g., compute the determinant exactly when m is below a constant.
[§5, proof of Theorem 1] The phase analysis states that variance is additive over iterations; this is correct because each recursive call uses fresh randomness, but the proof should present the conditional-expectation argument: E[X_i | history] telescopes to the total log-ratio, while the conditional variances add.

Assumptions & free parameters 0 free parameters · 7 assumptions · 0 invented entities

The algorithm uses fixed constants (0.8, 0.1, C=1/10) and a chosen block size k=Theta(epsilon sqrt(m)/log^3 m), but none of these are fitted to data or to the target count; they are design choices with proofs. No new physical or computational entities are postulated. 'Uncorrelated edge set' is a mathematical definition, not an entity requiring independent evidence.

assumptions (7)

standard math Kirchhoff's matrix tree theorem: T(G) = det^+(L(G))/n.
Used throughout Section 2 and Section 3 to connect spanning tree counts to Laplacian determinants.
standard math det(I - AA^T) = det(I - A^T A) for any matrix A.
Fact 3.1, used to turn the determinant expansion into a |F| by |F| determinant.
domain assumption Localization of electrical flows: the total correlation over any subset is O(||c||^2 log^2 n) (SRS18, Theorem 1.5).
Invoked in Lemma 4.3 to show that a random sample F+ has small total correlation, and therefore that a large uncorrelated subset exists.
domain assumption Nearly-linear time Laplacian solver (Spielman-Teng, Lemma 2.1).
Used in Lemmas 4.1 and 4.2 to compute leverage score estimates in O~(m) time.
domain assumption Leverage score estimation with multiplicative error (Spielman-Srivastava, Theorem 4).
Used in Figure 1 step 2 to identify edges with leverage score at most 0.8.
domain assumption L1-stable sketch with Cauchy random matrix (Indyk, Theorem 3).
Used in Lemma 4.3 to estimate column L1 norms of the correlation matrix.
standard math Chernoff and Markov bounds.
Used in Lemma 4.3 to control the quality of the sampled correlation matrix and in the phase analysis.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Approximate Spanning Tree Counting from Uncorrelated Edge Sets." pith.science (2026). https://pith.science/paper/THIFGL3Z

@misc{pith2026250514666,
  author       = {Pith},
  title        = {Pith review of: Approximate Spanning Tree Counting from Uncorrelated Edge Sets},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/THIFGL3Z}},
  note         = {Machine review of arXiv:2505.14666}
}

abstract

We show an $\widetilde{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 high probability, improving on the previous best runtime of $\widetilde{O}(m + n^{1.875}\epsilon^{-7/4})$ in sparse graphs. While previous algorithms were based on computing Schur complements and determinantal sparsifiers, our algorithm instead repeatedly removes sets of uncorrelated edges found using the electrical flow localization theorem of Schild-Rao-Srivastava [SODA 2018].

Figures

Figures reproduced from arXiv: 2505.14666 by the authors.

**Figure 1.** Our recursive algorithm for undirected graph spanning tree approximation Lemma 5.2. Let G = (V, E, w) be a graph with minimum degree ⩾ 3. Let F ⊆ E(G) be a subset of edges such that (1) all e ∈ F have leverage score at most 0.88, i.e., web(e) ⊤L †b(e) ⩽ 0.88, and (2) F is a ρ-correlated subset for ρ ⩽ 0.01. Consider running steps 4, 5 in the algorithm of [PITH_FULL_IMAGE:figures/full_fig_p010_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

19 extracted references · 18 canonical work pages

[5]

Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang

[BLL+21] Jan van den Brand, Yin Tat Lee, Yang P. Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang. Minimum cost flows, mdps, andℓ1-regression in nearly linear time for dense instances. In Samir Khuller and Virginia Vassilevska Williams, editors, STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June ...

work page 2021
[6]

Bipartite matching in nearly-linear time on moderately dense graphs

[BLN+20] Jan van den Brand, Yin Tat Lee, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang. Bipartite matching in nearly-linear time on moderately dense graphs. In Sandy Irani, editor,61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 919–930. IEEE,

work page 2020
[7]

[Bro89] Andrei Z. Broder. Generating random spanning trees. In30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October - 1 November 1989, pages 442–447. IEEE Computer Society,

work page 1989
[11]

Determinant-Preserving Sparsification of SDDM Matrices with Applications to Counting and Sampling Spanning Trees

Preliminary version appeared in FOCS‘17, available at:https://arxiv.org/abs/1705.00985. [FGL+21] Sebastian Forster, Gramoz Goranci, Yang P. Liu, Richard Peng, Xiaorui Sun, and Mingquan Ye. Minor sparsifiers and the distributed Laplacian paradigm. In62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Den- ver, CO, USA, February 7-10, ...

work page Pith review arXiv 2021
[12]

Minor Sparsifiers and the Distributed Laplacian Paradigm

Available at:https: //arxiv.org/abs/2012.15675. 12 [GLP21] Yu Gao, Yang P. Liu, and Richard Peng. Fully dynamic electrical flows: Sparse maxflow faster than goldberg-rao. In62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022, pages 516–527. IEEE,

work page Pith review arXiv 2012
[13]

Fully Dynamic Electrical Flows: Sparse Maxflow Faster Than Goldberg-Rao

Available athttps://arxiv.org/abs/2101.07233. [Ind06] Piotr Indyk. Stable distributions, pseudorandom generators, embeddings, and data stream computation.J. ACM, 53(3):307–323,

work page Pith review arXiv
[17]

An almost-linear time algorithm for uniform random spanning tree generation

Available at:https://arxiv.org/abs/1711.06455. [SRS18] Aaron Schild, Satish Rao, and Nikhil Srivastava. Localization of electrical flows. In Artur Czumaj, editor,Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 1577–1584. SIAM,

work page Pith review arXiv 2018
[18]

Localization of Electrical Flows

Available at:https://arxiv.org/abs/1708.01632. [SS11] Daniel A. Spielman and Nikhil Srivastava. Graph sparsification by effective resistances. SIAM J. Comput., 40(6):1913–1926,

work page Pith review arXiv 1913

Show all 19 references

[1989]

Modified log-sobolev inequalities for strongly log-concave distributions

[CGM19] Mary Cryan, Heng Guo, and Giorgos Mousa. Modified log-sobolev inequalities for strongly log-concave distributions. In David Zuckerman, editor,60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages ...

2019
[1993]

Spectral subspace sparsification

[LS18] Huan Li and Aaron Schild. Spectral subspace sparsification. In Mikkel Thorup, editor, 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 385–396. IEEE Computer Society,

2018
[2006]

Kelner and Aleksander Madry

[KM09] Jonathan A. Kelner and Aleksander Madry. Faster generation of random spanning trees. In50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, October 25-27, 2009, Atlanta, Georgia, USA, pages 13–21. IEEE Computer Society,

2009
[2014]

[V+13] Nisheeth K Vishnoi et al

Preliminary version appeared in STOC‘04, available at:http://arxiv.org/abs/cs/0607105. [V+13] Nisheeth K Vishnoi et al. Lx= b.Foundations and Trends®in Theoretical Computer Science, 8(1–2):1–141,
[2017]

[DPPR20] David Durfee, John Peebles, Richard Peng, and Anup B

Available at:https://arxiv.org/abs/1611.07451. [DPPR20] David Durfee, John Peebles, Richard Peng, and Anup B. Rao. Determinant-preserving sparsification of SDDM matrices.SIAM J. Comput., 49(4),

arXiv
[2018]

Fast generation of random spanning trees and the effective resistance metric

[MST15] Aleksander Madry, Damian Straszak, and Jakub Tarnawski. Fast generation of random spanning trees and the effective resistance metric. In Piotr Indyk, editor,Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA,...

2015
[2019]

Liu, and Thuy-Duong Vuong

11 [ALV22] Nima Anari, Yang P. Liu, and Thuy-Duong Vuong. Optimal sublinear sampling of span- ning trees and determinantal point processes via average-case entropic independence. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Den- ver, CO, USA, Oc...

2022
[2020]

Domain spar- sification of discrete distributions using entropic independence

[ADVY22] Nima Anari, Michal Derezinski, Thuy-Duong Vuong, and Elizabeth Yang. Domain spar- sification of discrete distributions using entropic independence. In Mark Braverman, editor,13th Innovations in Theoretical Computer Science Conference, ITCS 2022, Jan- uary 31 - Februar...

2022
[2021]

Log-concave polynomials II: high-dimensional walks and an FPRAS for counting bases of a matroid

[ALGV19] Nima Anari, Kuikui Liu, Shayan Oveis Gharan, and Cynthia Vinzant. Log-concave polynomials II: high-dimensional walks and an FPRAS for counting bases of a matroid. In Moses Charikar and Edith Cohen, editors,Proceedings of the 51st Annual ACM SIGACT Symposium on Theory ...

2019
[2022]

Log-concave polynomials IV: approximate exchange, tight mixing times, and near-optimal sampling of forests

[ALG+21] Nima Anari, Kuikui Liu, Shayan Oveis Gharan, Cynthia Vinzant, and Thuy-Duong Vuong. Log-concave polynomials IV: approximate exchange, tight mixing times, and near-optimal sampling of forests. In Samir Khuller and Virginia Vassilevska Williams, editors,STOC ’21: 53rd A...

2021
[2023]

[DKP+17] David Durfee, Rasmus Kyng, John Peebles, Anup B

Preliminary version appeared in FOCS‘18, available at:https://arxiv.org/abs/1805.12051. [DKP+17] David Durfee, Rasmus Kyng, John Peebles, Anup B. Rao, and Sushant Sachdeva. Sam- pling random spanning trees faster than matrix multiplication. In Hamed Hatami, Pierre McKenzie, an...

2017 arXiv

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [5]

Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang

[BLL+21] Jan van den Brand, Yin Tat Lee, Yang P. Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang. Minimum cost flows, mdps, andℓ1-regression in nearly linear time for dense instances. In Samir Khuller and Virginia Vassilevska Williams, editors, STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June ...

work page 2021

[2] [6]

Bipartite matching in nearly-linear time on moderately dense graphs

[BLN+20] Jan van den Brand, Yin Tat Lee, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang. Bipartite matching in nearly-linear time on moderately dense graphs. In Sandy Irani, editor,61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 919–930. IEEE,

work page 2020

[3] [7]

[Bro89] Andrei Z. Broder. Generating random spanning trees. In30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October - 1 November 1989, pages 442–447. IEEE Computer Society,

work page 1989

[4] [11]

Determinant-Preserving Sparsification of SDDM Matrices with Applications to Counting and Sampling Spanning Trees

Preliminary version appeared in FOCS‘17, available at:https://arxiv.org/abs/1705.00985. [FGL+21] Sebastian Forster, Gramoz Goranci, Yang P. Liu, Richard Peng, Xiaorui Sun, and Mingquan Ye. Minor sparsifiers and the distributed Laplacian paradigm. In62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Den- ver, CO, USA, February 7-10, ...

work page Pith review arXiv 2021

[5] [12]

Minor Sparsifiers and the Distributed Laplacian Paradigm

Available at:https: //arxiv.org/abs/2012.15675. 12 [GLP21] Yu Gao, Yang P. Liu, and Richard Peng. Fully dynamic electrical flows: Sparse maxflow faster than goldberg-rao. In62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022, pages 516–527. IEEE,

work page Pith review arXiv 2012

[6] [13]

Fully Dynamic Electrical Flows: Sparse Maxflow Faster Than Goldberg-Rao

Available athttps://arxiv.org/abs/2101.07233. [Ind06] Piotr Indyk. Stable distributions, pseudorandom generators, embeddings, and data stream computation.J. ACM, 53(3):307–323,

work page Pith review arXiv

[7] [17]

An almost-linear time algorithm for uniform random spanning tree generation

Available at:https://arxiv.org/abs/1711.06455. [SRS18] Aaron Schild, Satish Rao, and Nikhil Srivastava. Localization of electrical flows. In Artur Czumaj, editor,Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 1577–1584. SIAM,

work page Pith review arXiv 2018

[8] [18]

Localization of Electrical Flows

Available at:https://arxiv.org/abs/1708.01632. [SS11] Daniel A. Spielman and Nikhil Srivastava. Graph sparsification by effective resistances. SIAM J. Comput., 40(6):1913–1926,

work page Pith review arXiv 1913