Massively Parallel Symmetry Breaking on Sparse Graphs: MIS and Maximal Matching

• DOI: 10.48550/arxiv.1807.06701
• Publication Date: 2018-01-01
• Authors: Soheil Behnezhad; Mahsa Derakhshan; MohammadTaghi Haj...; Richard M. Karp
• Keywords: FOS: Computer and information sciences; Computer Science - Distributed, Parallel, and Cluster Computing; Computer Science - Data Structures and Algorithms; Data Structures and Algorithms (cs.DS); 0102 computer and information sciences; Distributed, Parallel, and Cluster Computing (cs.DC); 01 natural sciences

The success of modern parallel paradigms such as MapReduce, Hadoop, or Spark, has attracted a significant attention to the Massively Parallel Computation (MPC) model over past few years, especially on graph problems. In this work, we consider symmetry breaking problems maximal independent set (MIS) and matching (MM), which are among most intensively studied in distributed/parallel computing, MPC. These known admit efficient MPC algorithms if space per machine is near-linear $n$, number vertices graph. This requirement however, observed literature, often significantly larger than can afford; when input sparse. sharp contrast, truly sublinear regime $n^{1-Ω(1)}$ machine, all take $\log^{Ω(1)} n$ rounds considered inefficient. Motivated by shortcoming, parametrize our arboricity $α$ graph, well-received measure its sparsity. We show that both MIS MM $O(\sqrt{\log α}\cdot\log\log α+ \log^2\log n)$ round using $O(n^ε)$ for any constant $ε\in (0, 1)$ $\widetilde{O}(m)$ total space. Therefore, wide range sparse graphs with small arboricity---such minor-free graphs, bounded-genus bounded treewidth graphs---we get an $O(\log^2 \log algorithm exponentially improves prior algorithms. By reductions, results also imply $(1+ε)$-approximation maximum cardinality matching, $(2+ε)$-approximation weighted 2-approximation minimum vertex cover essentially same complexity memory requirements.