Massively Parallel Symmetry Breaking on Sparse Graphs: MIS and Maximal Matching
Massively Parallel Symmetry Breaking on Sparse Graphs: MIS and Maximal Matching
复制标题
稀疏图上的大规模并行对称性破缺：MIS 和最大匹配
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
R. Karp
中科院分区：
文献类型：
--
作者：
Soheil Behnezhad;Mahsa Derakhshan;M. Hajiaghayi;R. Karp
大规模并行计算（MPC）范例（如MapReduce）的成功引起了人们对更好地理解其真正计算能力的极大兴趣。在这方面的基本问题是如何利用这种模型的优势（例如，自由本地计算）来提高从传统的并行和分布式模型（如PRAM或ERAM）继承的算法的轮复杂度。最大独立集（MIS）或最大匹配等问题是该领域研究最深入的问题之一，自20世纪80年代以来，对数轮算法已经被称为这些问题。然而，在我们的工作之前，没有亚对数MPC算法已知的这些问题使用一个真正的次线性空间的$n^{1-\Omega（1）}$每台机器，其中$n$表示的顶点数。
我们的主要结果是一个真正的次线性算法，需要$O（\log \alpha + \log^2\log n）$轮计算MIS或最大匹配使用的最佳总空间$\tilde{O}（m）$其中$m$表示的边缘数和$\alpha$表示荫度的输入图。我们相信荫度参数化是特别有趣的MPC，因为大多数家庭的稀疏图有一个小荫度。我们的算法不假设荫度是常数，也不需要给定$\alpha$。这是第一次实质性的改进，在已知的PRAM/EQUIPMENT算法，这些问题上这样一个广泛的一类图。
由于树具有荫度1，我们的算法改进和推广了Brandt等人的最新算法。[arXiv：1802.06748]在$O（\log^3\log n）$轮中找到树上的MIS。此外，我们的算法的$n$-依赖性在Barenboim等人的相应的$O（\log \alpha + \sqrt{\log n}）$ PRAM/Bounds上呈指数级提高。[FOCS[12]和Ghaffari~[SODA'16]。
The success of massively parallel computation (MPC) paradigms such as MapReduce has led to a significant interest in better understanding their true computational power. The fundamental question in this regard is how the advantages of this model (e.g. free local computation) can be leveraged to improve the round-complexity of algorithms inherited from traditional parallel and distributed models such as PRAM or LOCAL. Problems such as maximal independent set (MIS) or maximal matching are among the most intensively studied problems in the field and logarithmic round algorithms have been known for these problems from 1980s. However, prior to our work, no sublogarithmic MPC algorithm was known for these problems using a truly sublinear space of $n^{1-\Omega(1)}$ per machine where $n$ denotes the number of vertices.
Our main result is a truly sublinear algorithm that takes $O(\log \alpha + \log^2\log n)$ rounds to compute MIS or maximal matching using an optimal total space of $\tilde{O}(m)$ where $m$ denotes the number of edges and $\alpha$ denotes the arboricity of the input graph. We believe parametrization by arboricity is particularly interesting for this regime of MPC since most families of sparse graphs have a small arboricity. Our algorithms do not assume arboricity is constant and do not require to be given $\alpha$. This is the first substantial improvement over the known PRAM/LOCAL algorithms for these problems on such a wide class of graphs.
Since trees have arboricity one, our algorithm improves and generalizes the recent algorithm of Brandt et al.~[arXiv:1802.06748] that finds MIS on trees in $O(\log^3\log n)$ rounds. Moreover, the $n$-dependency of our algorithm exponentially improves over the corresponding $O(\log \alpha + \sqrt{\log n})$ PRAM/LOCAL bounds by Barenboim et al.~[FOCS'12] and Ghaffari~[SODA'16].
用于估计平面图及其他区域中的匹配大小的流算法
DOI：
10.1145/3230819
发表时间：
2015
期刊：
ACM Transactions on Algorithms (TALG)
影响因子：
--
作者：
Hossein Esfandiari;Mohammad Taghi Hajiaghayi;Vahid Liaghat;Morteza Monemizadeh;Krzysztof Onak
通讯作者：
Krzysztof Onak
DOI：
10.1137/1.9781611974331.ch92
发表时间：
2016-01
期刊：
--
影响因子：
--
作者：
R. Chitnis;Graham Cormode;Hossein Esfandiari;M. Hajiaghayi;A. Mcgregor;M. Monemizadeh;Sofya Vorotnikova
通讯作者：
R. Chitnis;Graham Cormode;Hossein Esfandiari;M. Hajiaghayi;A. Mcgregor;M. Monemizadeh;Sofya Vorotnikova
核心集满足 EDCS：海量图上的匹配和顶点覆盖算法
DOI：
--
发表时间：
2019
期刊：
SODA 2019
影响因子：
--
作者：
Assadi, S.
Batenai
通讯作者：
Assadi, S.
Batenai