Approximate Spanning Tree Counting from Uncorrelated Edge Sets
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910957950730240 |
|---|---|
| author | Liu, Yang P. Peng, Richard Yang, Junzhao |
| author_facet | Liu, Yang P. Peng, Richard Yang, Junzhao |
| contents | We show an $\widetilde{O}(m^{1.5} ε^{-1})$ time algorithm that on a graph with $m$ edges and $n$ vertices outputs its spanning tree count up to a multiplicative $(1+ε)$ factor with high probability, improving on the previous best runtime of $\widetilde{O}(m + n^{1.875}ε^{-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]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_14666 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Approximate Spanning Tree Counting from Uncorrelated Edge Sets Liu, Yang P. Peng, Richard Yang, Junzhao Data Structures and Algorithms We show an $\widetilde{O}(m^{1.5} ε^{-1})$ time algorithm that on a graph with $m$ edges and $n$ vertices outputs its spanning tree count up to a multiplicative $(1+ε)$ factor with high probability, improving on the previous best runtime of $\widetilde{O}(m + n^{1.875}ε^{-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]. |
| title | Approximate Spanning Tree Counting from Uncorrelated Edge Sets |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2505.14666 |