Multiplicative Spanners in Minor-Free Graphs
Greg Bodwin, Gary Hoppenworth, Zihan Tan · 2025
Read Multiplicative Spanners in Minor-Free Graphs by Greg Bodwin, Gary Hoppenworth, Zihan Tan (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-16463.txt.
Introduction
Greg Bodwin, Gary Hoppenworth, and Zihan Tan wrote this 2025 computer science paper on sparse stand-in graphs called spanners. A spanner keeps near-true distances between points while using far fewer edges than the full graph. The graphs in focus are minor-free, meaning they exclude a fixed pattern as a minor.
A 2017 result showed that such graphs have light spanners that stretch distances by only a small factor. The new paper widens the trade-off between size and stretch. For any whole number k, the authors build a spanner with stretch 2k-1 and a sparsity bound that falls as k grows. A near variant keeps stretch near that level with a matching lightness bound. They also prove the exponent in their bound cannot be beaten, if a known girth conjecture holds. The proofs lean on a recent density result for minor-free graphs.
Catalog record
| CREATOR | Greg Bodwin, Gary Hoppenworth, Zihan Tan |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 34 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-16463
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Multiplicative Spanners in Minor-Free Graphs Greg Bodwin, Gary Hoppenworth, Zihan Tan Abstract 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 K_{h} -minor-free graph has a ( 1 + ε ) (1+{\varepsilon}) -spanner of lightness O ε ( h log h ) O_{{\varepsilon}}(h\sqrt{\log h}) , hence constant when h h and ε {\varepsilon} 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 k , every n n -node, K h K_{h} -minor-free graph has a ( 2 k − 1 ) (2k-1) -spanner with sparsity O ( h 2 k + 1 ⋅ polylog h ) , O\left(h^{\frac{2}{k+1}}\cdot\text{polylog }h\right), and a ( 1 + ε ) ( 2 k − 1 ) (1+{\varepsilon})(2k-1) -spanner with lightness O ε ( h 2 k + 1 ⋅ polylog h ) . O_{{\varepsilon}}\left(h^{\frac{2}{k+1}}\cdot\text{polylog }h\right). We further prove that this exponent 2 k + 1 \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. 1 Introduction Given an input graph G , a k -spanner is a sparse subgraph H whose shortest path distances agree with those of G up to a small multiplicative factor k , called the stretch . Spanners were introduced by Peleg and Schaffer [ PS89 ] after being used implicitly in prior work in distributed computing [ PU87 , PU89 ] , and have since found widespread application in network design, graph algorithms, etc (see survey [ ABS+20 ] ). A primary goal of research on spanners is to optimize the worst-case tradeoff between stretch and size . There are two popular ways to measure the size of a spanner: • The first is by its sparsity , |E(H)|/n (where n is the number of vertices in the input graph). This measure arises e.g. when the goal is to store the spanner in few bits of memory, or when running algorithms on the spanner whose runtime is sensitive to the spanner sparsity. • The second is by its total weight w(H) . Since w(H) can generally be unbounded, it is popular to normalize the spanner weight by the weight of a minimum spanning tree (MST) of the input graph: the lightness of a spanner H of a graph G is the quantity \ell(H\mid G):=\frac{w(H)}{w(\texttt{MST}(G))}. 1.1 Sparsity and Lightness in General Graphs The lightness of a graph is always at least as large as its sparsity, and in general it could be much higher. However, in some sense this difference can be bounded. Let us restrict attention to n -node metric graphs , in which every edge is the unique shortest path between its endpoints, which is the natural setting for spanner problems (i.e., non-metric edges can be removed without affecting the distances in G ). Here, the bounds are: Theorem 1 (Folklore) . Every n -node metric graph G has sparsity O(n) and lightness O(n^{2}) . For the upper bound on lightness, note that the graph G has at most n^{2} edges, each of weight at most w(\texttt{MST}(G)) . For the lower bound, consider an n -node path with edges of weight 1 , augmented with all additional edges where the weight of (u,v) is set to their distance along the path minus {\varepsilon} . Although this bound is tight, it has been known since the seminal work of Khuller, Raghavachari, and Young [ KRY95 ] that one can improve lightness to O(n) , matching sparsity, by paying a (1+{\varepsilon}) factor in stretch: Theorem 2 ( [ KRY95 ] ) . For any {\varepsilon}>0 , every n -node graph G has a (1+{\varepsilon}) -spanner with lightness O_{{\varepsilon}}(n) . 1 1 1 We use O_{{\varepsilon}} notation to hide polynomial dependencies on {\varepsilon}^{-1} . Once this initial upper bound is established, it is then natural to ask whether one can pay an even higher stretch to improve the O(n) sparsity and lightness dependence. After a long line of work [ ADD+93 , CDNS92 , ENS15a , CWN18 , FS20 , LS23 , Bod25 , BF25 ] , especially on the side of lightness, the following tradeoffs is now known: Theorem 3 ( [ ADD+93 , CWN18 , LS23 , Bod25 ] ) . For any {\varepsilon}>0 and positive integer k , every n -node graph has a (2k-1) -spanner with sparsity O(n^{1/k}) and a (1+{\varepsilon})(2k-1) -spanner with lightness O_{{\varepsilon}}(n^{1/k}) . This sparsity bound is known to be best possible, assuming the girth conjecture [ Erd63 ] . For lightness, the n^{1/k} dependence is tight assuming the girth conjecture as well. The exact (hidden) dependence on {\varepsilon} remains open, but it was recently proved that the {\varepsilon} -dependence is not entirely removable [ BF25 ] . 1.2 Sparsity and Lightness in Minor-Free Graphs An important special case for spanners is that where the input is K_{h} -minor-free; this arises as a technical tool in approximation algorithms for the Traveling Salesman Problem [ RS98 , AGK+98 , BDT14 , GS02 , DHK11 ] , and in some sense it generalizes the well-studied setting of Euclidean input graphs (see book [ NS07 ] ). A K_{h} -minor-free graph is already guaranteed to be quite sparse, and therefore comparably light: Theorem 4 ( [ Kos82 , AKS23 ] ) . Every n -node, K_{h} -minor-free metric graph has sparsity O(h\sqrt{\log h}) and lightness O(nh\sqrt{\log h}) . 2 2 2 For a gradual exposition of the proof and development of ideas in this theorem, we recommend the excellent recent blog post by Hung Le [ Le22 ] . Is is natural to ask, like for general graphs, whether one can remove the n -dependence from the lightness bound by paying an extra (1+{\varepsilon}) factor in the stretch. This was a long-standing open question: it was first asked in 2002 by Grigni and Sissokho [ GS02 ] , and then conjectured to be possible in 2012 by Grigni and Hung [ GH12 ] (who showed that (1+{\varepsilon}) stretch can be used to improve the dependence to \log n ). The result was finally achieved in a remarkable FOCS 2017 paper by Borradaille, Le, and Wulff-Nilsen: Theorem 5 ( [ BLWN17 ] ) . For any {\varepsilon}>0 , every n -node, K_{h} -minor-free graph has a (1+{\varepsilon}) -spanner with lightness O_{{\varepsilon}}(h\sqrt{\log h}) . Analogous to the work on general graphs, a natural next step after this theorem is to investigate the full tradeoff between stretch and sparsity/lightness for minor-free graphs. That is the subject of the current paper. We prove the following new bounds: Theorem 6 (Main Result, Upper Bounds) . For any {\varepsilon}>0 and 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+{\varepsilon})(2k-1) -spanner with lightness O_{{\varepsilon}}\left(h^{\frac{2}{k+1}}\cdot\text{polylog }h\right). The exponent \frac{2}{k+1} in Theorem 6 might look surprising; at first, one might guess that the exponent would be \frac{1}{k} to match Theorem 3 . However, we further prove that this is indeed