Speedup of Distributed Algorithms for Power Graphs in the CONGEST Model

Leonid Barenboim, Uri Goldenberg

פרסום מחקרי: פרק בספר / בדוח / בכנספרסום בספר כנסביקורת עמיתים

תקציר

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 אוק׳ 20241 נוב׳ 2024

סדרות פרסומים

שםLeibniz International Proceedings in Informatics, LIPIcs
כרך319
ISSN (מודפס)1868-8969

כנס

כנס38th International Symposium on Distributed Computing, DISC 2024
מדינה/אזורספרד
עירMadrid
תקופה28/10/241/11/24

הערה ביבליוגרפית

Publisher Copyright:
© Leonid Barenboim and Uri Goldenberg.

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Speedup of Distributed Algorithms for Power Graphs in the CONGEST Model'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי