Improved MPC Algorithms for MIS, Matching, and Coloring on Trees and Beyond

2020/02/22 by Mohsen Ghaffari, Christoph Grunau, Ghaffari, Mohsen +3 · 1 citation
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Optimization and Search Problems #Parallel #and Cluster Computing (cs.DC)

paper · pdf · doi:10.48550/arxiv.2002.09610

openalex publication_date 2020/02/22 · openalex created_date 2020/03/06 · openalex updated_date 2026/07/28

Abstract

We present O(loglog n) round scalable Massively Parallel Computation algorithms for maximal independent set and maximal matching, in trees and more generally graphs of bounded arboricity, as well as for constant coloring trees. Following the standards, by a scalable MPC algorithm, we mean that these algorithms can work on machines that have capacity/memory as small as n^δ for any positive constant δ<1. Our results improve over the O(log²log n) round algorithms of Behnezhad et al. [PODC'19]. Moreover, our matching algorithm is presumably optimal as its bound matches an Ω(loglog n) conditional lower bound of Ghaffari, Kuhn, and Uitto [FOCS'19].

Citations

• Locality in Distributed Graph Algorithms
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• MapReduce
• The Locality of Distributed Symmetry Breaking

Cited by

• Simulations between Strongly Sublinear MPC and Node-Capacitated Clique

Related

• Coloring Trees in Massively Parallel Computation
• Breaking the Linear-Memory Barrier in MPC: Fast MIS on Trees with Strongly Sublinear Memory
• Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover
• Massively Parallel Symmetry Breaking on Sparse Graphs: MIS and Maximal Matching
• Matching and MIS for Uniformly Sparse Graphs in the Low-Memory MPC Model