Minimum-weight Spanning Tree Construction in $O(\log \log \log n)$ Rounds on the Congested Clique

Sriram V Pemmaraju; Vivek B Sardeshmukh

doi:10.48550/arxiv.1412.2333

Back

$Minimum-weight Spanning Tree Construction in $O(\log \log \log n)$ Rounds on the Congested Clique$

Preprint

Open access

Minimum-weight Spanning Tree Construction in $O(\log \log \log n)$ Rounds on the Congested Clique

Sriram V Pemmaraju and Vivek B Sardeshmukh

ArXiv.org

12/07/2014

DOI: 10.48550/arxiv.1412.2333

Files and links (1)

url

https://doi.org/10.48550/arXiv.1412.2333View

Preprint (Author's original)This preprint has not been evaluated by subject experts through peer review. Preprints may undergo extensive changes and/or become peer-reviewed journal articles. Open Access

Abstract

This paper considers the \textit{minimum spanning tree (MST)} problem in the Congested Clique model and presents an algorithm that runs in $O(\log \log \log n)$ rounds, with high probability. Prior to this, the fastest MST algorithm in this model was a deterministic algorithm due to Lotker et al.~(SIAM J on Comp, 2005) from about a decade ago. A key step along the way to designing this MST algorithm is a \textit{connectivity verification} algorithm that not only runs in $O(\log \log \log n)$ rounds with high probability, but also has low message complexity. This allows the fast computation of an MST by running multiple instances of the connectivity verification algorithm in parallel. These results depend on a new edge-sampling theorem, developed in the paper, that says that if each edge $e = \{u, v\}$ is sampled independently with probability $c \log^2 n/\min\{\mbox{degree}(u), \mbox{degree}(v)\}$ (for a large enough constant $c$) then all cuts of size at least $n$ are approximated in the sampled graph. This sampling theorem is inspired by series of papers on graph sparsification via random edge sampling due to Karger~(STOC 1994), Bencz\'ur and Karger~(STOC 1996, arxiv 2002), and Fung et al.~(STOC 2011). The edge sampling techniques in these papers use probabilities that are functions of edge-connectivity or a related measure called edge-strength. For the purposes of this paper, these edge-connectivity measures seem too costly to compute and the main technical contribution of this paper is to show that degree-based edge-sampling suffices to approximate large cuts.

Computer Science - Distributed, Parallel, and Cluster Computing

Details

Title: Subtitle: Minimum-weight Spanning Tree Construction in $O(\log \log \log n)$ Rounds on the Congested Clique
Creators: Sriram V Pemmaraju
Vivek B Sardeshmukh
Resource Type: Preprint
Publication Details: ArXiv.org
DOI: 10.48550/arxiv.1412.2333
ISSN: 2331-8422
Language: English
Date posted: 12/07/2014
Academic Unit: Computer Science
Record Identifier: 9984411253202771

Metrics

2 Record Views