License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2020.15
URN: urn:nbn:de:0030-drops-124222
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12422/
Go to the corresponding LIPIcs Volume Portal

Bodwin, Greg ; Choudhary, Keerti ; Parter, Merav ; Shahar, Noa

New Fault Tolerant Subset Preservers

pdf-format:
LIPIcs-ICALP-2020-15.pdf (0.6 MB)

Abstract

Fault tolerant distance preservers are sparse subgraphs that preserve distances between given pairs of nodes under edge or vertex failures. In this paper, we present the first non-trivial constructions of subset distance preservers, which preserve all distances among a subset of nodes S, that can handle either an edge or a vertex fault.
- For an n-vertex undirected weighted graph or weighted DAG G = (V,E) and S ⊆ V, we present a construction of a subset preserver with Õ(|S|n) edges that is resilient to a single fault. In the single pair case (|S| = 2), the bound improves to O(n). We further provide a nearly-matching lower bound of Ω(|S|n) in either setting, and we show that the same lower bound holds conditionally even if attention is restricted to unweighted graphs.
- For an n-vertex directed unweighted graph G = (V,E) and r ∈ V, S ⊆ V, we present a construction of a preserver of distances in {r} × S with Õ(n^{4/3} |S|^{5/6}) edges that is resilient to a single fault. In the case |S| = 1 the bound improves to O(n^{4/3}), and for this case we provide another matching conditional lower bound.
- For an n-vertex directed weighted graph G = (V, E) and r ∈ V, S ⊆ V, we present a construction of a preserver of distances in {r} × S with Õ(n^{3/2} |S|^{3/4}) edges that is resilient to a single vertex fault. (It was proved in [Greg Bodwin et al., 2017] that the bound improves to O(n^{3/2}) when |S| = 1, and that this is conditionally tight.)

BibTeX - Entry

@InProceedings{bodwin_et_al:LIPIcs:2020:12422,
  author =	{Greg Bodwin and Keerti Choudhary and Merav Parter and Noa Shahar},
  title =	{{New Fault Tolerant Subset Preservers}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{15:1--15:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Artur Czumaj and Anuj Dawar and Emanuela Merelli},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12422},
  URN =		{urn:nbn:de:0030-drops-124222},
  doi =		{10.4230/LIPIcs.ICALP.2020.15},
  annote =	{Keywords: Subset Preservers, Distances, Fault-tolerance}
}

Keywords: Subset Preservers, Distances, Fault-tolerance
Collection: 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Issue Date: 2020
Date of publication: 29.06.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI