Andoni, Alexandr ;
Stein, Clifford ;
Zhong, Peilin
Log Diameter Rounds Algorithms for 2Vertex and 2Edge Connectivity
Abstract
Many modern parallel systems, such as MapReduce, Hadoop and Spark, can be modeled well by the MPC model. The MPC model captures well coarsegrained computation on large data  data is distributed to processors, each of which has a sublinear (in the input data) amount of memory and we alternate between rounds of computation and rounds of communication, where each machine can communicate an amount of data as large as the size of its memory. This model is stronger than the classical PRAM model, and it is an intriguing question to design algorithms whose running time is smaller than in the PRAM model.
In this paper, we study two fundamental problems, 2edge connectivity and 2vertex connectivity (biconnectivity). PRAM algorithms which run in O(log n) time have been known for many years. We give algorithms using roughly log diameter rounds in the MPC model. Our main results are, for an nvertex, medge graph of diameter D and bidiameter D', 1) a O(log D log log_{m/n} n) parallel time 2edge connectivity algorithm, 2) a O(log D log^2 log_{m/n}n+log D'log log_{m/n}n) parallel time biconnectivity algorithm, where the bidiameter D' is the largest cycle length over all the vertex pairs in the same biconnected component. Our results are fully scalable, meaning that the memory per processor can be O(n^{delta}) for arbitrary constant delta>0, and the total memory used is linear in the problem size. Our 2edge connectivity algorithm achieves the same parallel time as the connectivity algorithm of [Andoni et al., 2018]. We also show an Omega(log D') conditional lower bound for the biconnectivity problem.
BibTeX  Entry
@InProceedings{andoni_et_al:LIPIcs:2019:10590,
author = {Alexandr Andoni and Clifford Stein and Peilin Zhong},
title = {{Log Diameter Rounds Algorithms for 2Vertex and 2Edge Connectivity}},
booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
pages = {14:114:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771092},
ISSN = {18688969},
year = {2019},
volume = {132},
editor = {Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10590},
URN = {urn:nbn:de:0030drops105906},
doi = {10.4230/LIPIcs.ICALP.2019.14},
annote = {Keywords: parallel algorithms, biconnectivity, 2edge connectivity, the MPC model}
}
04.07.2019
Keywords: 

parallel algorithms, biconnectivity, 2edge connectivity, the MPC model 
Seminar: 

46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Issue date: 

2019 
Date of publication: 

04.07.2019 