Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their Applications
share
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].
READ FULL TEXT