2026-07-21T03:18:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22673 2026-04-17T05:32:08Z ddc:004 open_access

Distributed and Parallel Low-Diameter Decompositions for Arbitrary and Restricted Graphs Dou, Jinfeng Götte, Thorsten Hillebrandt, Henning Scheideler, Christian Werthmann, Julian Distributed Graph Algorithms Network Decomposition Excluded Minor We consider the distributed and parallel construction of low-diameter decompositions with strong diameter. We present algorithms for arbitrary undirected, weighted graphs and also for undirected, weighted graphs that can be separated through k ∈ Õ(1) shortest paths. This class of graphs includes planar graphs, graphs of bounded treewidth, and graphs that exclude a fixed minor K_r. Our algorithms work in the PRAM, CONGEST, and the novel HYBRID communication model and are competitive in all relevant parameters. Given 𝒟 > 0, our low-diameter decomposition algorithm divides the graph into connected clusters of strong diameter 𝒟. For an arbitrary graph, an edge e ∈ E of length 𝓁_e is cut between two clusters with probability O(𝓁_e⋅log(n)/𝒟). If the graph can be separated by k ∈ Õ(1) paths, the probability improves to O(𝓁_e⋅log(log n)/𝒟). In either case, the decompositions can be computed in Õ(1) depth and Õ(m) work in the PRAM and Õ(1) time in the HYBRID model. In CONGEST, the runtimes are Õ(HD + √n) and Õ(HD) respectively. All these results hold w.h.p. Broadly speaking, we present distributed and parallel implementations of sequential divide-and-conquer algorithms where we replace exact shortest paths with approximate shortest paths. In contrast to exact paths, these can be efficiently computed in the distributed and parallel setting [STOC '22]. Further, and perhaps more importantly, we show that instead of explicitly computing vertex-separators to enable efficient parallelization of these algorithms, it suffices to sample a few random paths of bounded length and the nodes close to them. Thereby, we do not require complex embeddings whose implementation is unknown in the distributed and parallel setting. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jinfeng Dou and Thorsten Götte and Henning Hillebrandt and Christian Scheideler and Julian Werthmann 2025 Is Part Of LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2025.45 urn:nbn:de:0030-drops-226734 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.45 eng https://creativecommons.org/licenses/by/4.0/legalcode