Massively Parallel Algorithm for Minimum Weight Vertex Cover

Massively Parallel Computation (MPC) model for solving the Minimum Weight Vertex Cover problem efficiently, including optimal round complexities and known approximation ratios. The algorithm is designed for graphs with vertices and edges, with each machine processing data synchronously in rounds. Various memory regimes are explored, emphasizing the significance of Minimum Weight Vertex Cover in NP-hard problems.

• Parallel Computing
• Algorithm
• Minimum Weight
• Vertex Cover
• MPC

cal_in Follow

Uploaded on Sep 17, 2024 | 0 Views

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.

Presentation Transcript

1. A Massively Parallel Algorithm for Minimum Weight Vertex Cover Mohsen Ghaffari ETH Zurich Ce Jin Daan Nilis ETH Zurich Tsinghua U. SPAA 2020

2. 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

3. Massively Parallel Computation (MPC) Model Input: Graph ? with ? vertices and ? edges ? machines each with memory ?. ( ? ? ? + ? ) Three memory regimes (for constant 0 < ? < 1): ? = ?1+? (strongly super-linear) ?((loglog?)2)-round (1 + ?)-apx Maximum Matching easy ?(1)-round Maximal Matching [Lattanzi-Moseley-Suri-Vassilvitskii, SPAA 11] [Czumaj- cki-M dry-Mitrovi -Onak-Sankowski, STOC 18] ?(loglog?)-round (1 + ?)-apx Maximum Matching ? = ? (near-linear) [Ghaffari-Gouleakis-Konrad-Mitrovi -Rubinfeld, PODC 18] [Assadi-Bateni-Bernstein-Mirrokni-Stein, SODA 19] [Behnezhad-Hajiaghayi-Harris, FOCS'19] ?(loglog?)-round Maximal Matching ?(loglog?)-round (1 + ?)-apx Maximum Weight Matching [Gamlath-Kale-Mitrovi -Svensson, PODC'19] ? = ?? ?( log?)-round Maximal Matching [Ghaffari-Uitto, SODA'19] hard (strongly sub-linear)

4. Minimum Vertex Cover Problem A vertex cover of an undirected graph ? = ?,? is a subset ? ? such that every edge ? ? has at least one endpoint in ?. NP-hard. Best known apx-ratio: 2 (optimal under Unique Games Conjecture) In near-linear memory regime of MPC model: (image from Wikipedia) ?(loglog?)-round (2 + ?)-apx MinVC [Ghaffari-Gouleakis-Konrad-Mitrovi -Rubinfeld, PODC 18] ?(loglog?)-round Maximal Matching 2-apx MinVC [Behnezhad-Hajiaghayi-Harris, FOCS'19] Minimum Weight Vertex Cover: Each vertex ? ? has a weight ? ? > 0. Find the vertex cover ? with minimum total weight ? ??(?). Best known round complexity: ?(log?) (by simulating PRAM algorithms in MPC)

5. Our result (? = # vertices, ? = # edges) In near-linear regime of MPC (each machine has memory ? = ? ), we can compute a (2 + ?)-apx Minimum Weight Vertex Cover in ?(??????? ?) rounds (with high probability). (2? ? ? 1) Faster than previous ?(loglog?)-round algorithms when e.g. ? = ? 2(log log ?)2. (average degree) (max degree) We follow the framework of Ghaffari et al. [PODC 18] for (unweighted) VC, with some crucial changes to (1) handle the weighted case, and, (2) improve the round complexity.

6. LOCAL Algorithm via Primal-Dual First consider unweighted case (? ? = 1 for all ?). Every edge ? has a weight ? ? > 0. Define ?(?) ? ?? ? (total incident weight of ?). Maintain ? ? 1 for all ?. (i.e., ?( ) is a fractional matching) Initialization: ? ? 1/ for all ?. All edges are active. while at least one edge is active: for each active vertex ? with ? ? 1 ? : Freeze ? and its incident edges for each active edge ?: ? ? ?(?)/(1 ?) Return all frozen vertices as a vertex cover Active edges ? have ? ? = 1 / 1 ?#rounds Terminates in ?(log ) rounds 1 ? Size VC ? VC? ? 2 ?? ? 2 Size(MinVC) (Weak Duality)

7. MPC algorithm [Ghaffari et al., PODC18] Round Compression idea [Czumaj et al. STOC 18] In each phase: ? 1/[active ? ? ] (active degree ?) w.h.p. each machine has ?(?) edges in its induced subgraph Randomly partition the active vertices among ? machines Each machine simulates the LOCAL algo for ? = (log?) rounds until ? drops below log20?. Finally solve the remaining sparse graph on one machine After ? 0.05log1/(1 ?)? rounds, active edges have ? ? ? ? ?0.05. So ? ??.??after this phase. (initially ? = ?) #phases = ? ??????? ? ?,? ? ? ? ?,? + ? ?,? on the same machine frozen ? Instead of checking ? ? 1 ?, pick random thresholds ?? 1 2?,1 ? and check ? ? ??. Use ? ? as an estimate of ?(?) during simulation.

8. Fewer Partitions We can partition the active vertices among ? machines (instead of ?), where 1 ? ? active? ? (?(?) is the active degree of ?) The memory bound still holds: ? w.h.p. each machine ??has ?(?) edges in its induced subgraph. 2 probability of landing in ??. 2= ? . Every edge has 1/ ? ?[ #edges in ??] = ?/ When ? log2?, we can show a high probability bound. ? Fewer partitons Faster progress

9. LOCAL Algorithm: Weighted Case Maintain ? ? ?(?) for all ?. (i.e., ?( ) is a fractional matching) Assume ? ? 1. Every edge ? has a weight ? ? > 0. Define ?(?) ? ?? ? (total incident weight of ?). Initialization: ? ? 1/ for all ? = (?,?). All edges are active. while at least one edge is active: for each active vertex ? with ? ? 1 ? ?(?): Freeze ? and its incident edges for each active edge ?: ? ? ?(?)/(1 ?) Return all frozen vertices as a vertex cover Active edges ? have ? ? = 1 / 1 ?#rounds Terminates in ?(log ? ) rounds

10. LOCAL Algorithm: Weighted Case Maintain ? ? ?(?) for all ?. (i.e., ?( ) is a fractional matching) Assume ? ? 1. Every edge ? has a weight ? ? > 0. Define ?(?) ? ?? ? (total incident weight of ?). ?(?) ?(?),?(?) Initialization: ? ? ??? for all ? = (?,?). All edges are active. ?(?) while at least one edge is active: for each active vertex ? with ? ? 1 ? ?(?): Freeze ? and its incident edges for each active edge ?: ? ? ?(?)/(1 ?) Return all frozen vertices as a vertex cover Initially it s a valid fractional matching Terminates in ?(log ) rounds

11. MPC Round Complexity In each phase: ?(?) ?(?),?(?) 1 ? ? active? ? (?(?) is the active degree of ?) Randomly partition the active vertices among ? machines Each machine simulates the LOCAL algo for ? = (log?) rounds until ? drops below log20?. ?init? ??? ? ?(?) (initially ? = 2?/?) #phases = ? ??????(?/?) Claim: After this phase, ? drops to ?(?0.95). Proof: Orient the edge (?,?) from ? to ? iff ?(?) ?(?)<?(?) ? ? ? ? ?(?)at the beginning. / 1 ?? outdeg ? ?(?) ? ? ? ?+ ? ? ?(?)/ 1 ??. After ? rounds, ? ? ? ? outdeg ? ? ? 1 ??= ?(?)/?0.05. So #edges = ?outdeg ? ??/?0.05.

12. Ignoring Low-degree Vertices Issue: Edges with low-degree endpoints have big weights. This affects the concentration of ?(?). ?(?) ?(?),?(?) ?init? ??? ?(?) ? ?,? ? ? ? ?,? + ? ?,? on the same machine frozen ? Use ? ? as an estimate of ?(?) during simulation. Solution: Only consider vertices with degree ? ? ?0.95. Other vertices are inactive in this phase (may become active in later phases). We can still make progress: #[ inactive edges] ? ?0.95 #[other edges] ? ?0.95 (shown in the previous slide) ? drops to ? ?0.95 after this phase

13. Summary Non-uniform initialization of edge weights Analysis of progress via orienting edges Ignoring low-degree vertices Open Problem 2-approximate (? = ?) minimum weight vertex cover? Thank you!