Deterministic replacement path covering

C. S. Karthik, Merav Parter

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Scopus citations

Abstract

In this article, we provide a unified and simplified approach to derandomize central results in the area of fault-tolerant graph algorithms. Given a graph G, a vertex pair (s, t) ∈ V (G) × V (G), and a set of edge faults F ⊆ E(G), a replacement path P(s, t, F) is an s-t shortest path in G \F. For integer parameters L, f, a replacement path covering (RPC) is a collection of subgraphs of G, denoted by GL,f = {G1,..., Gr}, such that for every set F of at most f faults (i.e., |F| ≤ f) and every replacement path P(s, t, F) of at most L edges, there exists a subgraph Gi ∈ GL,f that contains all the edges of P and does not contain any of the edges of F. The covering value of the RPC GL,f is then defined to be the number of subgraphs in GL,f. In the randomized setting, it is easy to build an (L, f)RPC with covering value of O(max{L, f}min{L,f}·min{L, f}· log n), but to this date, there is no efficient deterministic algorithm with matching bounds. As noted recently by Alon, Chechik, and Cohen (ICALP 2019) this poses the key barrier for derandomizing known constructions of distance sensitivity oracles and fault-tolerant spanners. We show the following: • There exist efficient deterministic constructions of (L, f)-RPCs whose covering values almost match the randomized ones, for a wide range of parameters. Our time and value bounds improve considerably over the previous construction of Parter (DISC 2019). Our algorithms are based on the introduction of a novel notion of hash families that we call Hit and Miss hash families. We then show how to construct these hash families from (algebraic) error correcting codes such as Reed-Solomon codes and Algebraic-Geometric codes. • For every L, f, and n, there exists an n-vertex graph G whose (L, f)-RPC covering value is Ω(Lf). This lower bound is obtained by exploiting connections to the problem of designing sparse fault-tolerant BFS structures. An applications of our above deterministic constructions is the derandomization of the algebraic construction of the distance sensitivity oracle by Weimann and Yuster (FOCS 2010). The preprocessing and query time of our deterministic algorithm nearly match the randomized bounds. This resolves the open problem of Alon, Chechik and Cohen (ICALP 2019). Additionally, we show a derandomization of the randomized construction of vertex fault-tolerant spanners by Dinitz and Krauthgamer (PODC 2011) and Braunschvig et al. (Theor. Comput. Sci., 2015). The time complexity and the size bounds of the output spanners nearly match the randomized counterparts.

Original languageEnglish (US)
Title of host publicationACM-SIAM Symposium on Discrete Algorithms, SODA 2021
EditorsDaniel Marx
PublisherAssociation for Computing Machinery
Pages704-723
Number of pages20
ISBN (Electronic)9781611976465
StatePublished - 2021
Externally publishedYes
Event32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021 - Alexandria, Virtual, United States
Duration: Jan 10 2021Jan 13 2021

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Conference

Conference32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021
Country/TerritoryUnited States
CityAlexandria, Virtual
Period1/10/211/13/21

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint

Dive into the research topics of 'Deterministic replacement path covering'. Together they form a unique fingerprint.

Cite this