Lower bounds on collective additive spanners
Derek G. Corneil, Feodor F. Dragan, Ekkehard Köhler, Yang Xiang · 2025
Read Lower bounds on collective additive spanners by Derek G. Corneil, Feodor F. Dragan, Ekkehard Köhler, Yang Xiang (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-18508.txt.
Description
A spanner is a sparse stand-in for a graph that keeps distances nearly honest, and a collective spanner is a small team of trees that covers for each other. Derek Corneil and co-authors map the limits of such teams in this 2025 paper, proving lower bounds for several graph families. Their results say some graphs simply cannot be covered cheaply.
Unit interval graphs already force many trees for the tightest error. Strongly chordal and chordal graphs defeat any fixed-size team at small errors, and weakly chordal and outerplanar graphs defeat it at every error level. A companion result blocks shrinking treewidth while spanning. The authors say the bounds complete the picture left by known constructions.
Catalog record
| CREATOR | Derek G. Corneil, Feodor F. Dragan, Ekkehard Köhler, Yang Xiang |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 70 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-18508