EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

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

Yi-Jun Chang

ACM Transactions on Algorithms · 31.07.2026 · 22 (3) · 1-44

DOI: 10.1145/3805031 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Algorithms, online erschienen am 03.06.2026. Verfasst von Yi-Jun Chang. Die Arbeit nennt 66 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

In the \(\textsf{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 \(\textsf{CONGEST}\) model via expander routing . Consequently, in such networks, many problems that admit efficient \(\textsf{LOCAL}\) algorithms via low-diameter decomposition can also be solved efficiently in \(\textsf{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\} \nonumber\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\}\nonumber \end{align*}\) rounds in the \(\textsf{CONGEST}\) model for networks excluding a fixed minor. Our algorithm has a wide range of applications, including the following results in \(\textsf{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 et al. [PODC 2018].

Zitieren

APA

Chang, Y. (2026). Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their Applications. ACM Transactions on Algorithms, 22(3), 1-44. https://doi.org/10.1145/3805031

Vancouver

Chang Y. Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their Applications. ACM Transactions on Algorithms. 2026;22(3):1-44. doi:10.1145/3805031

BibTeX
@article{Chang2026,
  author = {Chang, Yi-Jun},
  title = {Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their Applications},
  journal = {ACM Transactions on Algorithms},
  year = {2026},
  volume = {22},
  number = {3},
  pages = {1--44},
  doi = {10.1145/3805031}
}
Kostenlos starten →