Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their Applications

DOI10.1145/3583668.3594604MaRDI QIDQ6202221zbMATH OpenOpenAlexWikidataFDO

Authors Yi-Jun Chang

Publication date 26 March 2024

Published in Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2304.04699

zbMATH Keywords

distributed approximationexpander decompositionproperty testing

Mathematics Subject Classification ID

Distributed systems (68M14) Distributed algorithms (68W15)

Abstract: In the LOCAL model, low-diameter decomposition is a useful tool in designing algorithms, as it allows us to shift from the general graph setting to the low-diameter graph setting, where brute-force information gathering can be done efficiently. Recently, Chang and Su [PODC 2022] showed that any high-conductance network excluding a fixed minor contains a high-degree vertex, so the entire graph topology can be gathered to one vertex efficiently in the CONGEST model using expander routing. Therefore, in networks excluding a fixed minor, many problems that can be solved efficiently in LOCAL via low-diameter decomposition can also be solved efficiently in CONGEST via expander decomposition. In this work, we show improved decomposition and routing algorithms for networks excluding a fixed minor in the CONGEST model. Our algorithms cost $extpoly(logn,1/epsilon)$ rounds deterministically. For bounded-degree graphs, our algorithms finish in $O(epsilo{n}^{-1}logn)+epsilo{n}^{-O(1)}$ rounds. Our algorithms have a wide range of applications, including the following results in CONGEST. 1. A $(1-epsilon)$-approximate maximum independent set in a network excluding a fixed minor can be computed deterministically in $O(epsilo{n}^{-1}lo{g}^{a}stn)+epsilo{n}^{-O(1)}$ rounds, nearly matching the $Omega(epsilo{n}^{-1}lo{g}^{a}stn)$ lower bound of Lenzen and Wattenhofer [DISC 2008]. 2. Property testing of any additive minor-closed property can be done deterministically in $O(logn)$ rounds if $epsilon$ is a constant or $O(epsilo{n}^{-1}logn)+epsilo{n}^{-O(1)}$ rounds if the maximum degree $Delta$ is a constant, nearly matching the $Omega(epsilo{n}^{-1}logn)$ lower bound of Levi, Medina, and Ron [PODC 2018].

Cites work

• A local constant factor MDS approximation for bounded genus graphs
• A strengthened analysis of a local algorithm for the minimum dominating set problem in planar graphs
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• Cops, robbers, and threatening skeletons: padded decomposition for minor-free graphs
• Deterministic coin tossing with applications to optimal parallel list ranking
• Distributed algorithms for planar networks. I: Planar embedding
• Distributed algorithms for planar networks. II: Low-congestion shortcuts, MST, and Min-Cut
• Distributed Almost Exact Approximations for Minor-Closed Families
• Distributed approximation algorithms for k-dominating set in graphs of bounded genus and linklessly embeddable graphs
• Distributed Computing
• Distributed Computing: A Locality-Sensitive Approach
• Distributed Dominating Set Approximations beyond Planar Graphs
• Distributed minimum dominating set approximations in restricted families of graphs
• Distributed MST and routing in almost mixing time
• Distributed Strong Diameter Network Decomposition
• Excluded minors, network decomposition, and multicommodity flow
• Fast Distributed Approximations in Planar Graphs
• Faster distributed shortest path approximations via shortcuts
• Graph minors. XX: Wagner's conjecture
• scientific article; zbMATH DE number 7561283 (Why is no real title available?)
• Leveraging Linial’s Locality Limit
• Local algorithms for bounded degree sparsifiers in sparse graphs
• Locality in Distributed Graph Algorithms
• Low diameter graph decompositions
• Low-congestion shortcuts without embedding
• Minor excluded network families admit fast distributed algorithms
• Near-optimal distributed DFS in planar graphs
• Near-optimal Distributed Triangle Enumeration via Expander Decompositions
• Near-optimal low-congestion shortcuts on bounded parameter graphs
• On the complexity of local distributed graph problems
• Planar diameter via metric compression
• Polylogarithmic-time deterministic network decomposition and distributed derandomization
• Property testing of planarity in the \textsf{CONGEST} model
• Round- and message-optimal distributed graph algorithms
• Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition
• The extremal function for complete minors
• The power of distributed verifiers in interactive proofs
• Tight Analyses of Two Local Load Balancing Algorithms

Cited in

(4)

• Distributed model checking on graphs of bounded treedepth
• The distributed complexity of locally checkable labeling problems beyond paths and trees
• Narrowing the \textsf{LOCAL-CONGEST} gaps in sparse networks via expander decompositions
• Efficient distributed decomposition and routing algorithms in minor-free networks and their applications

This page was built for publication: Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their Applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6202221)