2026-07-24T02:01:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13116 2024-03-06T10:51:36Z ddc:004 open_access

Distributed Planar Reachability in Nearly Optimal Time Parter, Merav Distributed Graph Algorithms Planar Graphs Reachability 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]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Merav Parter 2020 Is Part Of LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2020.38 urn:nbn:de:0030-drops-131160 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.38 eng https://creativecommons.org/licenses/by/3.0/legalcode