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

In the \ (LOCAL\) model of distributed computing, low-diameter decomposition is a fundamental tool for algorithm design, as it enables a reduction from general graphs to low-diameter graphs where brute-force information gathering can be performed efficiently. Chang and Su PODC 2022 showed that any high-conductance network excluding a fixed minor contains a high-degree vertex \ (v^\), allowing the entire graph topology to be gathered at \ (v^\) efficiently in the \ (CONGEST\) model via expander routing. Consequently, in such networks, many problems that admit efficient \ (LOCAL\) algorithms via low-diameter decomposition can also be solved efficiently in \ (CONGEST\) using expander decomposition. In this work, we present improved decomposition and routing algorithms for networks excluding a fixed minor. We define an \ ( (, D, T) \) -decomposition of a graph \ (G= (V, E) \) as a partition of \ (V\) into clusters of diameter at most \ (D\), with at most \ (|E|\) inter-cluster edges, such that information gathering within each cluster can be completed in \ (T\) rounds in parallel. We show that an \ ( (, D, T) \) -decomposition with \ (align D=O (^-1) T=\2^{O (^{21) } O (), \ poly (^-1, ) \} align\) can be computed deterministically in \ (align O (^-1^n) +\2^{O (^{21) } O (), \ poly (^-1, ) \} align\) rounds in the \ (CONGEST\) model for networks excluding a fixed minor. Our algorithm has a wide range of applications, including the following results in \ (CONGEST\): A \ ( (1-) \) -approximate maximum independent set in networks excluding a fixed minor can be computed deterministically in \ (O (^-1^n) +poly (^-1) \) rounds, nearly matching the \ ( (^-1^n) \) lower bound of Lenzen and Wattenhofer DISC 2008. Property testing of any additive minor-closed property can be performed deterministically in \ (O (n) \) rounds for constant \ (\), or in \ (O (^-1 n) +poly (^-1) \) rounds for constant \ (\), nearly matching the \ ( (^-1 n) \) lower bound of Levi, Medina, and Ron PODC 2018.