License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2017.74
URN: urn:nbn:de:0030-drops-74510
URL: http://drops.dagstuhl.de/opus/volltexte/2017/7451/
Go to the corresponding LIPIcs Volume Portal


Georgiadis, Loukas ; Graf, Daniel ; Italiano, Giuseppe F. ; Parotsidis, Nikos ; Uznanski, Przemyslaw

All-Pairs 2-Reachability in O(n^w log n) Time

pdf-format:
LIPIcs-ICALP-2017-74.pdf (0.7 MB)


Abstract

In the 2-reachability problem we are given a directed graph G and we wish to determine if there are two (edge or vertex) disjoint paths from u to v, for given pair of vertices u and v. In this paper, we present an algorithm that computes 2-reachability information for all pairs of vertices in O(n^w log n) time, where n is the number of vertices and w is the matrix multiplication exponent. Hence, we show that the running time of all-pairs 2-reachability is only within a log factor of transitive closure. Moreover, our algorithm produces a witness (i.e., a separating edge or a separating vertex) for all pair of vertices where 2-reachability does not hold. By processing these witnesses, we can compute all the edge- and vertex-dominator trees of G in O(n^2) additional time, which in turn enables us to answer various connectivity queries in O(1) time. For instance, we can test in constant time if there is a path from u to v avoiding an edge e, for any pair of query vertices u and v, and any query edge e, or if there is a path from u to v avoiding a vertex w, for any query vertices u, v, and w.

BibTeX - Entry

@InProceedings{georgiadis_et_al:LIPIcs:2017:7451,
  author =	{Loukas Georgiadis and Daniel Graf and Giuseppe F. Italiano and Nikos Parotsidis and Przemyslaw Uznanski},
  title =	{{All-Pairs 2-Reachability in O(n^w log n) Time}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{74:1--74:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7451},
  URN =		{urn:nbn:de:0030-drops-74510},
  doi =		{10.4230/LIPIcs.ICALP.2017.74},
  annote =	{Keywords: 2-reachability, All Dominator Trees, Directed Graphs, Boolean Matrix Multiplication}
}

Keywords: 2-reachability, All Dominator Trees, Directed Graphs, Boolean Matrix Multiplication
Seminar: 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Issue Date: 2017
Date of publication: 06.07.2017


DROPS-Home | Fulltext Search | Imprint Published by LZI