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(ε⁻¹) T=min\{2^{O(log²1/ε)}· O(logΔ),\ poly(ε⁻¹,log Δ)\} {align}\) can be computed deterministically in \({align} O(ε⁻¹log^{}n)+min\{2^{O(log²1/ε )}· O(logΔ),\ poly(ε⁻¹,logΔ)\} {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(ε⁻¹log^{}n)+poly(ε⁻¹)\) rounds, nearly matching the \(Ω(ε⁻¹log^{}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 \(ε\) , or in \(O(ε⁻¹log n)+poly(ε⁻¹)\) rounds for constant \(Δ\) , nearly matching the \(Ω(ε⁻¹log n)\) lower bound of Levi, Medina, and Ron [PODC 2018].