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

In the \(\mathsf{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^{\star}\) , allowing the entire graph topology to be gathered at \(v^{\star}\) efficiently in the \(\mathsf{CONGEST}\) model via expander routing . Consequently, in such networks, many problems that admit efficient \(\mathsf{LOCAL}\) algorithms via low-diameter decomposition can also be solved efficiently in \(\mathsf{CONGEST}\) using expander decomposition . In this work, we present improved decomposition and routing algorithms for networks excluding a fixed minor. We define an \((\epsilon,D,T)\) -decomposition of a graph \(G=(V,E)\) as a partition of \(V\) into clusters of diameter at most \(D\) , with at most \(\epsilon|E|\) inter-cluster edges, such that information gathering within each cluster can be completed in \(T\) rounds in parallel. We show that an \((\epsilon,D,T)\) -decomposition with \(\begin{align} D=O(\epsilon^{-1})\quad\text{and}\quad T=\min\left\{2^{O\left(\log^{2}\frac{1} {\epsilon}\right)}\cdot O(\log\Delta),\ \operatorname{poly}(\epsilon^{-1},\log \Delta)\right\} \end{align}\) can be computed deterministically in \(\begin{align} O(\epsilon^{-1}\log^{\ast}n)+\min\left\{2^{O\left(\log^{2}\frac{1}{\epsilon} \right)}\cdot O(\log\Delta),\ \operatorname{poly}(\epsilon^{-1},\log\Delta)\right\} \end{align}\) rounds in the \(\mathsf{CONGEST}\) model for networks excluding a fixed minor. Our algorithm has a wide range of applications, including the following results in \(\mathsf{CONGEST}\) : A \((1-\epsilon)\) -approximate maximum independent set in networks excluding a fixed minor can be computed deterministically in \(O(\epsilon^{-1}\log^{\ast}n)+\operatorname{poly}(\epsilon^{-1})\) rounds, nearly matching the \(\Omega(\epsilon^{-1}\log^{\ast}n)\) lower bound of Lenzen and Wattenhofer [DISC 2008]. Property testing of any additive minor-closed property can be performed deterministically in \(O(\log n)\) rounds for constant \(\epsilon\) , or in \(O(\epsilon^{-1}\log n)+\operatorname{poly}(\epsilon^{-1})\) rounds for constant \(\Delta\) , nearly matching the \(\Omega(\epsilon^{-1}\log n)\) lower bound of Levi, Medina, and Ron [PODC 2018].