DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2026.31

Unconditional Lower Bounds for Degree Fault Tolerant Spanners

Authors: Greg Bodwin and Aleksey Lopez

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

Abstract

We study multiplicative graph spanners in the f-degree fault tolerant (f-DFT) model, in which the spanner must approximately preserve distances even after any subset of edges of maximum degree f temporarily "fails" and is removed from the graph. We prove that there are n-node lower bound graphs for which any f-DFT (2k-1)-stretch spanner H must have size |E(H)| ≥ Ω(f^{1-1/k} n^{1+1/k}) . This matches a lower bound that was previously only known to hold conditionally, under the 1963 girth conjecture of Erdős. It also matches the current upper bounds, up to a factor of exp(k). Our proof is an analysis of the so-called Wenger graphs (J. Comb. Theory 1991), via their recent reinterpretation by Szabó and by Conlon (Am. Math. Monthly 2021).

Cite as

Greg Bodwin and Aleksey Lopez. Unconditional Lower Bounds for Degree Fault Tolerant Spanners. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 31:1-31:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bodwin_et_al:LIPIcs.ESA.2026.31,
  author =	{Bodwin, Greg and Lopez, Aleksey},
  title =	{{Unconditional Lower Bounds for Degree Fault Tolerant Spanners}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{31:1--31:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.31},
  URN =		{urn:nbn:de:0030-drops-271673},
  doi =		{10.4230/LIPIcs.ESA.2026.31},
  annote =	{Keywords: Spanners, Fault Tolerance, Girth Conjecture, Wenger Graphs}
}

Search Results

Documents authored by Lopez, Aleksey

Unconditional Lower Bounds for Degree Fault Tolerant Spanners

Abstract

Cite as

Thanks for your feedback!

Could not send message