תקציר
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 Gk with certain properties into O(R · ∆k/2-1)-round CONGEST algorithms for Gk. 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 Gk and exponential improvement for G2. 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(∆4)-coloring of G2 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.[25] that required O(∆ + log∗ n) rounds, and the standard simulation of Linial [30] algorithm in Gk that required O(∆ · log∗ n) rounds. We devise an algorithm for O(∆2)-coloring of G2 with O(∆ · log ∆ + log∗ n) rounds, and (∆2 + 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. [25]. For k > 2, our running time for O(∆2k)-coloring of Gk is O(k · ∆k/2-1 · log ∆ · log∗ n). Our running time for O(∆k)-coloring of Gk 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 Gk nearly matches the lower bound of Fraigniaud, Halldorsson and Nolin.
שפה מקורית | אנגלית |
---|---|
כותר פרסום המארח | 38th International Symposium on Distributed Computing, DISC 2024 |
עורכים | Dan Alistarh |
מוציא לאור | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
מסת"ב (אלקטרוני) | 9783959773522 |
מזהי עצם דיגיטלי (DOIs) | |
סטטוס פרסום | פורסם - 24 אוק׳ 2024 |
אירוע | 38th International Symposium on Distributed Computing, DISC 2024 - Madrid, ספרד משך הזמן: 28 אוק׳ 2024 → 1 נוב׳ 2024 |
סדרות פרסומים
שם | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|
כרך | 319 |
ISSN (מודפס) | 1868-8969 |
כנס
כנס | 38th International Symposium on Distributed Computing, DISC 2024 |
---|---|
מדינה/אזור | ספרד |
עיר | Madrid |
תקופה | 28/10/24 → 1/11/24 |
הערה ביבליוגרפית
Publisher Copyright:© Leonid Barenboim and Uri Goldenberg.