Faster Set Cover in the MPC Model
Hongyan Ji, Shreyas Pai, Sriram V. Pemmaraju, Joshua Z. Sobel · Theoretical Computer Science · 2025
The Massively Parallel Computation (MPC) model is a popular abstraction for large-scale distributed computing. The Set Cover problem is a classical combinatorial optimization problem that has a wide variety of applications and generalizes many well-studied problems such as vertex cover, edge cover, and minimum dominating set. For a Set Cover instance with a ground set of n elements and a collection of m sets, we present two O (log n )-approximation algorithms in the MPC model. Our algorithms run in O ˜ ( log N ) -rounds in the linear-memory MPC model and in O ˜ ( log 1.5 N ) rounds in the sublinear-memory MPC model, where N = n + m . These are the first O (log n )-approximation algorithms for Set Cover in this setting that run in o (log 2 N ) rounds. Our results are obtained by repurposing the sparsified graph exponentiation technique that has been successful for the maximal independent set problem in the MPC model and applying it to a simple, distributed Set Cover algorithm by Grunau, Mitrović, Rubinfeld, and Vakilian (SODA 2020).