Improved MPC Algorithms for MIS, Matching, and Coloring on Trees and Beyond
This research focuses on Massively Parallel Computation (MPC) algorithms for various graph optimization problems such as Maximal Matching, Maximal Independent Set, and Vertex Coloring on trees and sparse graphs. The study presents efficient algorithms with reduced round complexities, demonstrating advancements in parallel computing models. The work addresses different memory regimes, arboricity-based graph structures, and colorings tailored for specific graph properties like sparsity. The findings highlight novel approaches and lower bounds in the context of MPC for graph optimization.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Improved MPC Algorithms for MIS, Matching, and Coloring on Trees and Beyond Christoph Grunau ETH Zurich Ce Jin Mohsen Ghaffari ETH Zurich Tsinghua MIT DISC 2020
Massively Parallel Computation (MPC) Model Input: Graph ? with ? vertices and ? edges ? machines each with memory ?. ( ? ? ? + ? ) Computation proceeds in synchronous rounds Optimize the round complexity Supports many primitives in ? 1 rounds: sorting, prefix sum, array queries, etc. [Goodrich-Sitchinava- Zhang 11, ] Total data sent ? Total data received ? Input graph partitioned among ? machines Round 1 Round 2
MPC: Maximal Matching and Maximal Independent Set Three memory regimes (for constant 0 < ? < 1): easy ?(1)-round Maximal Matching ?(1)-round Maximal Independent Set ? = ?1+? [Lattanzi-Moseley-Suri-Vassilvitskii, SPAA 11] [Harvey-Liaw-Liu, SPAA 18] (strongly super-linear) ?(loglog?)-round Maximal Independent Set ? = ? (near-linear) [Ghaffari-Gouleakis-Konrad-Mitrovi -Rubinfeld, PODC 18] ?(loglog?)-round Maximal Matching [Behnezhad-Hajiaghayi-Harris, FOCS'19] ? = ?? ?( log?)-round Maximal Matching & MIS [Ghaffari-Uitto, SODA'19] (strongly sub-linear) Conditional lower bound: loglog? rounds. [Ghaffari-Kuhn-Uitto, FOCS 19] hard
MM and MIS on Sparse graphs (MPC local memory ??(0 < ? < 1), global memory ? + ? polylog?) ? (loglog?3)-round MIS on trees ? (loglog?2)-round MIS & MM on bounded-arboricity graphs [Behnezhad-Brandt-Derakhshan-Fischer-Hajiaghayi-Karp-Uitto, PODC 19] [Brandt-Fischer-Uitto, SIROCCO 19] This work: ?(???????)-round MIS & MM on bounded-arboricity graphs Arboricity ?(?): minimum number of forests that the edges of ? can be partitioned into. ?(?) small: ? is sparse everywhere Matches the [GKU 19] conditional lower bound for Maximal Matching, which even holds for trees (? = ?)
Vertex Coloring (MPC local memory ??(0 < ? < 1), global memory ? + ? polylog?) ?(logloglog?)-round ( + 1)-coloring [Chang-Fischer-Ghaffari-Uitto-Zheng, PODC 19] + [Rozho -Ghaffari, STOC 20] Use fewer colors for sparse graphs? A graph with arboricity ? has a 2?-coloring. (For ? = ?(1): a coloring algorithm implies MIS/MM algorithms) There are ?(log?)-round LOCAL algo for ? ? -coloring [Barenboim-Elkin, PODC 08] [Ghaffari-Lymouri, DISC 17] Open question: polyloglog?-round MPC constant-coloring on graphs with ? = ?(1)? This work: ?(???????)-round 4-coloring on trees, with ?(?) global memory
MIS & MM [Behnezhad et al. PODC19] Step 1: Degree-reduction : Find a matching (or independent set) of ?, such that: After removal, the remaining graph has max degree poly(?,log?) Step 1: ?((loglog?)2) rounds We improve Step 1 to ? ??????? rounds! Step 2: Apply the ? the remaining graph. Combine the solutions and return. log -round MPC algorithm [Ghaffari-Uitto 19] to solve Step 2: ?( log? + loglog? rounds
Step 1: Degree-reduction [Behnezhad et al. PODC19] A LOCAL black box [Barenboim-Elkin-Pettie-Schneider, FOCS 12] (Messages and state descriptions have length polylog?) (Applicable when poly(?,log?) ) Let ??denote the set of vertices in ? with degree > In ?(?) LOCAL rounds we can find a matching (or indep. set) in ?, such that w.h.p. the remaining graph ? satisfies ?? |??|/? After log ? executions (a phase ): max degree is reduced to . After ?(loglog ) phases: max degree is reduced to poly(?,log?).
Simulate LOCAL in MPC: first attempt Round Compression via graph exponentiation - If the ?-hop neighborhood of ? can be stored into one machine, then we can simulate ? LOCAL rounds for ?, in ?(1) MPC rounds! - Collect the ?-hop neighborhood in ?(log?) MPC rounds, by doubling the radius in each round. Phase 1 has ?(log ?) LOCAL rounds Let radius ? = ? log ?. Neighborhood size ? ??. Simulate phase 1 in ?(1) MPC rounds, reducing max degree to = Double the radius: ? = ? log ? = 2?, and simulate phase 2 (and so on ) - Total round complexity ? loglog? - Global memory: ? ??+?+ ? .
Smaller global memory [Behnezhad et al. PODC19] ? {?:deg ? > Black box: ?(1) LOCAL rounds, ? |?|/? }. In every phase of degree reduction: - Only collect the neighborhoods of high-deg vertices ? ?. - Other vertices are irrelevant in the current phase. Reduce ? and increase radius ?, keeping global memory ? ? ?(?) After 1st execution of the black box: ? ?/ . Radius ? = 1 After 2nd execution: ? ?/ 2. Radius ? = 2 ?(?) MPC rounds: 2?executions finished: ? ?/ 2?. Radius ? = 2? (phase finished after ? loglog?) Downside: In next phase, we have to collect the neighborhoods from scratch! Total round complexity: ?(loglog? loglog ) Maintain radius ? = (# LOCAL rounds finished)
Our solution [Behnezhad et al. PODC 19] Each phase: ?(loglog?) MPC rounds Phase 1 Phase 2 Phase loglog MPC timeline Many vertices already became irrelevant in phase 1 Start phase 2 (collecting neighborhoods & simulation) on these vertices earlier! [Our pipelined algorithm] Phase 1 Phase 2 ?(loglog? + ? loglog ) MPC rounds in total! Phase 3 ?-round lag Previous two algorithms correspond to ? = 0 and ? = (loglog?) We will choose ? = ? ? ,while being able to keep global memory ? ? + ?
Pipelined algorithm ?1 {?:deg ? > 1/2} ?2 {?:deg ? > 1/4} ?3 {?:deg ? > 1/8} Black box: ?(1) LOCAL rounds. Phase ?: ?? Phase 1 |??|/ 1/2? 1 Phase 2 ?-round lag Phase 3 MPC timeline ? At time ?: Phase 1: finished ?1= 2?executions. Radius ?1= 2? Phase 2: finished ?2= 2? ?executions. Radius ?2= 2? ? Phase 3: finished ?3= 2? 2?executions. Radius ?3= 2? 2? When simulating phase ?, in the ideal (unpipelined) scenario, (1) Max degree in phase ? already dropped below ? 1 1/2? 1 (2) Relevant ?? ?/ ? 1 However, we may encounter pending vertices that are still relevant in previous phases ? < ?, and may have degree ? 1 ??. Each relevant vertex has neighborhood size ? 1 ??.
Pending vertices Seems the memory bound breaks down Can we simply ignore pending vertices? No Later they may turn out to be relevant. Can t afford to collect their neighborhoods from scratch again! Plan: - Continue to collect and grow their neighborhoods as usual. We can show the global & local memory bounds still hold! - LOCAL simulation: States are marked as pending actual states ( removed / active ) at the beginning of the phase will be revealed as soon as they finish previous phases.
Black box: ?(1) LOCAL rounds. Phase ?: ?? |??|/ ? 1 ? 1/2? Memory analysis When simulating phase ?, if ? is a pending vertex, then: - ? ??for some previous phase ? < ?. (deg(?) ( ?, ? 1]) - Or, ? is close to some vertex in ??(because pending states will propagate when simulating phase ?). If we have simulated ??executions in phase ?, then close means distance ? ?? . Find the highest degree vertex ? that is close to ?. Suppose deg (?) ?, ? 1,? ?? Then ? is reachable from ? by an ?(??)-step path, on which every vertex has degree ? 1. The number of such ? is |??| ? 1 ? ??. ??+ 1 ?<?|??| ? 1 ? ?? Non-pending + pending vertices in total: ?? ?/ ? 1 ??) ? 1 ?? ? ?? ? 1 ?? + 1 ?<?|??| ? 1 Total size of ??-hop neighborhoods (?/ ? 1
Memory analysis ?? global memory for phase ? ?/ ? 1 ?? ??+ 1 ?<?|??| ? 1 ? ??+?? For phase ? maintain ??= ??/? (for some constant ? 2) . (??= number of LOCAL blackbox executions = 2? ? 1 ?at time ?) (?? = radius of collected neighborhoods) Simple induction shows (after setting big enough constants ?,?): Global memory for phase ? is at most ?/?? ? ?/? ??.
(? 1/2?) Global Memory At time ?, for phase ?: Finished ??= 2? ? 1 ?executions of the black box. Radius ??= ??/? (for some constant ? 2) . ?/2 ?? Induction hypothesis: |??| ?/ ? 1 ?? Total memory for phase ? ?/ ? 1 (? 1)??+ 1 ?<??/ ? 1 ?/ ? 1 ?? ?? 1= 2? ??= 2? ??? ?? ??+ 1 ?<?|??| ? 1 ? ?? Pick big enough constant ? ?/? ?? ? ?? ?/ ? 1 ?/2 ?? Dominated by a geometric series
Local memory ?? Recall: In phase ? vertex ? s neighborhood requires ? 1 if ? is close to some vertices in ?? ? < ? . ?/2 ??. local memory, We ve shown |??| ?/ ? 1 ?/2 ??> ? 1 ?/2 ??. Then ?? 1 implies ? ? 1 Set ? > 2/? . Then local memory ??.
Conclusion Key idea: Use pipelining to reduce round complexity, while keeping near-linear global memory. Open Questions Does our technique have other applications? Is there a polyloglog?-round MPC algorithm that can color constant-arboricity graphs using ?(1) colors? Thank you!
