2026-07-22T07:15:32Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21233 2024-10-24T07:40:07Z ddc:004 open_access

Speedup of Distributed Algorithms for Power Graphs in the CONGEST Model Barenboim, Leonid Goldenberg, Uri Distributed Algorithms Graph Coloring Power Graph CONGEST We obtain improved distributed algorithms in the CONGEST message-passing setting for problems on power graphs of an input graph G. This includes Coloring, Maximal Independent Set, and related problems. For R = f(Δ^k,n), we develop a general deterministic technique that transforms R-round LOCAL model algorithms for G^k with certain properties into O(R ⋅ Δ^{k/2-1})-round CONGEST algorithms for G^k. This improves the previously-known running time for such transformation, which was O(R⋅Δ^{k-1}). Consequently, for problems that can be solved by algorithms with the required properties and within polylogarithmic number of rounds, we obtain quadratic improvement for G^k and exponential improvement for G². We also obtain significant improvements for problems with larger number of rounds in G. Notable implications of our technique are the following deterministic distributed algorithms: - We devise a distributed algorithm for O(Δ⁴)-coloring of G² whose number of rounds is O(log Δ + log^* n). This improves exponentially (in terms of Δ) the best previously-known deterministic result of Halldorsson, Kuhn and Maus.[M. M. Halldorson et al., 2020] that required O(Δ + log^{*}n) rounds, and the standard simulation of Linial [N. Linial, 1992] algorithm in G^k that required O(Δ ⋅ log^* n) rounds. - We devise an algorithm for O(Δ²)-coloring of G² with O(Δ ⋅ log Δ + log^*n) rounds, and (Δ²+1)-coloring with O(Δ^{1.5} ⋅ log Δ + log^*n) rounds. This improves quadratically, and by a power of 4/3, respectively, the best previously-known results of Halldorsson, Khun and Maus. [M. M. Halldorson et al., 2020]. - For k > 2, our running time for O(Δ^{2k})-coloring of G^k is O(k⋅Δ^{k/2-1}⋅log Δ⋅log^* n). Our running time for O(Δ^k)-coloring of G^k is Õ(k⋅Δ^{k-1}⋅log^* n). This improves best previously-known results quadratically, and by a power of 3/2, respectively. - For constant k > 2, our upper bound for O(Δ^{2k})-coloring of G^k nearly matches the lower bound of Fraigniaud, Halldorsson and Nolin. [P. Fraigniaud et al., 2020] for checking the correctness of a coloring in G^k. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Leonid Barenboim and Uri Goldenberg 2024 Is Part Of LIPIcs, Volume 319, 38th International Symposium on Distributed Computing (DISC 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2024.6 urn:nbn:de:0030-drops-212337 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.6 eng https://creativecommons.org/licenses/by/4.0/legalcode