Vertex Fault-Tolerant Emulators

Greg Bodwin, Michael Dinitz, Yasamin Nazari

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

Abstract

A k-spanner of a graph G is a sparse subgraph that preserves its shortest path distances up to a multiplicative stretch factor of k, and a k-emulator is similar but not required to be a subgraph of G. A classic theorem by Althöfer et al. [Disc. Comp. Geom.'93] and Thorup and Zwick [JACM'05] shows that, despite the extra flexibility available to emulators, the size/stretch tradeoffs for spanners and emulators are equivalent. Our main result is that this equivalence in tradeoffs no longer holds in the commonly-studied setting of graphs with vertex failures. That is: we introduce a natural definition of vertex fault-tolerant emulators, and then we show a three-way tradeoff between size, stretch, and fault-tolerance for these emulators that polynomially surpasses the tradeoff known to be optimal for spanners. We complement our emulator upper bound with a lower bound construction that is essentially tight (within log n factors of the upper bound) when the stretch is 2k − 1 and k is either a fixed odd integer or 2. We also show constructions of fault-tolerant emulators with additive error, demonstrating that these also enjoy significantly improved tradeoffs over those available for fault-tolerant additive spanners.
Original languageEnglish
Title of host publication13th Innovations in Theoretical Computer Science Conference, ITCS 2022
EditorsM. Braverman
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959772174
DOIs
Publication statusPublished - 1 Jan 2022
Externally publishedYes
Event13th Innovations in Theoretical Computer Science Conference, ITCS 2022 - Berkeley, United States
Duration: 31 Jan 20223 Feb 2022

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969

Conference

Conference13th Innovations in Theoretical Computer Science Conference, ITCS 2022
Country/TerritoryUnited States
CityBerkeley
Period31/01/223/02/22

Funding

Funding Michael Dinitz: Supported in part by NSF award CCF-1909111. Yasamin Nazari: Supported in part by NSF award CCF-1909111 and by Austrian Science Fund (FWF) grant P 32863-N.

FundersFunder number
National Science FoundationCCF-1909111
Austrian Science FundP 32863-N

    Fingerprint

    Dive into the research topics of 'Vertex Fault-Tolerant Emulators'. Together they form a unique fingerprint.

    Cite this