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

CREATORDerek G. Corneil, Feodor F. Dragan, Ekkehard Köhler, Yang Xiang
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE70 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-18508

Browse the full library · About the Tower of Babel