2023/04/10 by Yi‐Jun Chang, Chang, Yi-Jun
Computer Science · Materials Science · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Graphene research and applications #Interconnection Networks and Systems #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2304.04699
openalex publication_date 2023/04/10 · openalex created_date 2023/04/12 · openalex updated_date 2026/07/28
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 poly(log n, 1/ε) rounds deterministically. For bounded-degree graphs, our algorithms finish in O(ε-1log n) + ε-O(1) rounds. Our algorithms have a wide range of applications, including the following results in CONGEST. 1. A (1-ε)-approximate maximum independent set in a network excluding a fixed minor can be computed deterministically in O(ε-1log^∗ n) + ε-O(1) rounds, nearly matching the Ω(ε-1log^∗ n) lower bound of Lenzen and Wattenhofer [DISC 2008]. 2. Property testing of any additive minor-closed property can be done deterministically in O(log n) rounds if ε is a constant or O(ε-1log n) + ε-O(1) rounds if the maximum degree Δ is a constant, nearly matching the Ω(ε-1log n) lower bound of Levi, Medina, and Ron [PODC 2018].