2021/05/05 by Konrad, Christian, Pemmaraju, Sriram V., Riaz, Talal +1
#Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)
paper · doi:10.48550/arxiv.2105.01833
The goal of this paper is to understand the complexity of symmetry breaking problems, specifically maximal independent set (MIS) and the closely related β-ruling set problem, in two computational models suited for large-scale graph processing, namely the k-machine model and the graph streaming model. We present a number of results. For MIS in the k-machine model, we improve the O(m/k2 + Δ/k)-round upper bound of Klauck et al. (SODA 2015) by presenting an O(m/k2)-round algorithm. We also present an Ω(n/k2) round lower bound for MIS, the first lower bound for a symmetry breaking problem in the k-machine model. For β-ruling sets, we use hierarchical sampling to obtain more efficient algorithms in the k-machine model and also in the graph streaming model. More specifically, we obtain a k-machine algorithm that runs in O(βnΔ1/β/k2) rounds and, by using a similar hierarchical sampling technique, we obtain one-pass algorithms for both insertion-only and insertion-deletion streams that use O(β⋅ n^1+1/2β-1) space. The latter result establishes a clear separation between MIS, which is known to require Ω(n2) space (Cormode et al., ICALP 2019), and β-ruling sets, even for β= 2. Finally, we present an even faster 2-ruling set algorithm in the k-machine model, one that runs in O(n/k2-ε + k1-ε) rounds for any ε, 0 ≤ ε≤ 1.