Epic Fail: Emulators Can Tolerate Polynomially Many Edge Faults for Free

Greg Bodwin, Michael Dinitz, Yasamin Nazari

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

Abstract

A t-emulator of a graph G is a graph H that approximates its pairwise shortest path distances up to multiplicative t error. We study fault tolerant t-emulators, under the model recently introduced by Bodwin, Dinitz, and Nazari [ITCS 2022] for vertex failures. In this paper we consider the version for edge failures, and show that they exhibit surprisingly different behavior. In particular, our main result is that, for (2k − 1)-emulators with k odd, we can tolerate a polynomial number of edge faults for free. For example: for any n-node input graph, we construct a 5-emulator (k = 3) on O(n4/3) edges that is robust to f = O(n2/9) edge faults. It is well known that Ω(n4/3) edges are necessary even if the 5-emulator does not need to tolerate any faults. Thus we pay no extra cost in the size to gain this fault tolerance. We leave open the precise range of free fault tolerance for odd k, and whether a similar phenomenon can be proved for even k.
Original languageEnglish
Title of host publication14th Innovations in Theoretical Computer Science Conference, ITCS 2023
EditorsY.T. Kalai
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959772631
DOIs
Publication statusPublished - 1 Jan 2023
Externally publishedYes
Event14th Innovations in Theoretical Computer Science Conference, ITCS 2023 - Cambridge, United States
Duration: 10 Jan 202313 Jan 2023

Publication series

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

Conference

Conference14th Innovations in Theoretical Computer Science Conference, ITCS 2023
Country/TerritoryUnited States
CityCambridge
Period10/01/2313/01/23

Funding

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

FundersFunder number
National Science FoundationCCF-1909111, CCF-2153680
Austrian Science FundP 32863-N

    Fingerprint

    Dive into the research topics of 'Epic Fail: Emulators Can Tolerate Polynomially Many Edge Faults for Free'. Together they form a unique fingerprint.

    Cite this