Multiplicative Spanners in Minor-Free Graphs
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_ | 1866912342941368320 |
|---|---|
| author | Bodwin, Greg Hoppenworth, Gary Tan, Zihan |
| author_facet | Bodwin, Greg Hoppenworth, Gary Tan, Zihan |
| contents | In FOCS 2017, Borradaille, Le, and Wulff-Nilsen addressed a long-standing open problem by proving that minor-free graphs have light spanners. Specifically, they proved that every $K_h$-minor-free graph has a $(1+ε)$-spanner of lightness $O_ε(h \sqrt{\log h})$, hence constant when $h$ and $ε$ are regarded as constants.
We extend this result by showing that a more expressive size/stretch tradeoff is available. Specifically: for any positive integer $k$, every $n$-node, $K_h$-minor-free graph has a $(2k-1)$-spanner with sparsity \[O\left(h^{\frac{2}{k+1}} \cdot \text{polylog } h\right),\] and a $(1+ε)(2k-1)$-spanner with lightness \[O_ε\left(h^{\frac{2}{k+1}} \cdot \text{polylog } h \right).\] We further prove that this exponent $\frac{2}{k+1}$ is best possible, assuming the girth conjecture. At a technical level, our proofs leverage the recent improvements by Postle (2020) to the remarkable density increment theorem for minor-free graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_16463 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Multiplicative Spanners in Minor-Free Graphs Bodwin, Greg Hoppenworth, Gary Tan, Zihan Data Structures and Algorithms In FOCS 2017, Borradaille, Le, and Wulff-Nilsen addressed a long-standing open problem by proving that minor-free graphs have light spanners. Specifically, they proved that every $K_h$-minor-free graph has a $(1+ε)$-spanner of lightness $O_ε(h \sqrt{\log h})$, hence constant when $h$ and $ε$ are regarded as constants. We extend this result by showing that a more expressive size/stretch tradeoff is available. Specifically: for any positive integer $k$, every $n$-node, $K_h$-minor-free graph has a $(2k-1)$-spanner with sparsity \[O\left(h^{\frac{2}{k+1}} \cdot \text{polylog } h\right),\] and a $(1+ε)(2k-1)$-spanner with lightness \[O_ε\left(h^{\frac{2}{k+1}} \cdot \text{polylog } h \right).\] We further prove that this exponent $\frac{2}{k+1}$ is best possible, assuming the girth conjecture. At a technical level, our proofs leverage the recent improvements by Postle (2020) to the remarkable density increment theorem for minor-free graphs. |
| title | Multiplicative Spanners in Minor-Free Graphs |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2504.16463 |