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.2016.130
URN: urn:nbn:de:0030-drops-62659
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6265/
Go to the corresponding LIPIcs Volume Portal

Choudhary, Keerti

An Optimal Dual Fault Tolerant Reachability Oracle

pdf-format:
LIPIcs-ICALP-2016-130.pdf (0.8 MB)

Abstract

Let G=(V,E) be an n-vertices m-edges directed graph. Let s inV be any designated source vertex. We address the problem of reporting the reachability information from s under two vertex failures. We show that it is possible to compute in polynomial time an O(n) size data structure that for any query vertex v, and any pair of failed vertices f_1, f_2, answers in O(1) time whether or not there exists a path from s to v in G\{f_1,f_2}.

For the simpler case of single vertex failure such a data structure can be obtained using the dominator-tree from the celebrated work of Lengauer and Tarjan [TOPLAS 1979, Vol. 1]. However, no efficient data structure was known in the past for handling more than one failures. We, in addition, also present a labeling scheme with O(log^3(n))-bit size labels such that for any f_1, f_2, v in V , it is possible to determine in poly-logarithmic time if v is reachable from s in G\{f_1,f_2} using only the labels of f1, f_2 and v.

Our data structure can also be seen as an efficient mechanism for verifying double-dominators. For any given x, y, v in V we can determine in O(1) time if the pair (x,y) is a double-dominator of v. Earlier the best known method for this problem was using dominator chain from which verification of double-dominators of only a single vertex was possible.

BibTeX - Entry

@InProceedings{choudhary:LIPIcs:2016:6265,
  author =	{Keerti Choudhary},
  title =	{{An Optimal Dual Fault Tolerant Reachability Oracle}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{130:1--130:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6265},
  URN =		{urn:nbn:de:0030-drops-62659},
  doi =		{10.4230/LIPIcs.ICALP.2016.130},
  annote =	{Keywords: Fault tolerant, Directed graph, Reachability oracle, Labeling scheme}
}

Keywords: Fault tolerant, Directed graph, Reachability oracle, Labeling scheme
Collection: 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Issue Date: 2016
Date of publication: 23.08.2016

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