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.DISC.2020.38
URN: urn:nbn:de:0030-drops-131160
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13116/
Go to the corresponding LIPIcs Volume Portal

Parter, Merav

Distributed Planar Reachability in Nearly Optimal Time

pdf-format:
LIPIcs-DISC-2020-38.pdf (0.8 MB)

Abstract

We present nearly optimal distributed algorithms for fundamental reachability problems in planar graphs. In the single-source reachability problem given is an n-vertex directed graph G = (V,E) and a source node s, it is required to determine the subset of nodes that are reachable from s in G. We present the first distributed reachability algorithm for planar graphs that runs in nearly optimal time of Õ(D) rounds, where D is the undirected diameter of the graph. This improves the complexity of Õ(D²) rounds implied by the recent work of [Li and Parter, STOC'19].

We also consider the more general reachability problem of identifying the strongly connected components (SCCs) of the graph. We present an Õ(D)-round algorithm that computes for each node in the graph an identifier of its strongly connected component in G. No non-trivial upper bound for this problem (even in general graphs) has been known before.

Our algorithms are based on characterizing the structural interactions between balanced cycle separators. We show that the reachability relations between separator nodes can be compressed due to a Monge-like property of their directed shortest paths. The algorithmic results are obtained by combining this structural characterization with the recursive graph partitioning machinery of [Li and Parter, STOC'19].

BibTeX - Entry

@InProceedings{parter:LIPIcs:2020:13116,
  author =	{Merav Parter},
  title =	{{Distributed Planar Reachability in Nearly Optimal Time}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{38:1--38:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Hagit Attiya},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/13116},
  URN =		{urn:nbn:de:0030-drops-131160},
  doi =		{10.4230/LIPIcs.DISC.2020.38},
  annote =	{Keywords: Distributed Graph Algorithms, Planar Graphs, Reachability}
}

Keywords: Distributed Graph Algorithms, Planar Graphs, Reachability
Collection: 34th International Symposium on Distributed Computing (DISC 2020)
Issue Date: 2020
Date of publication: 07.10.2020

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