Narrowing the LOCAL-CONGEST Gaps in Sparse Networks via Expander Decompositions
Narrowing the LOCAL-CONGEST Gaps in Sparse Networks via Expander Decompositions
复制标题
通过扩展器分解缩小稀疏网络中的局部拥塞差距
DOI：
10.1145/3519270.3538423
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Su, Hsin-Hao
中科院分区：
文献类型：
--
作者：
Chang, Yi-Jun;Su, Hsin-Hao
许多组合优化问题，包括最大加权匹配和最大独立集，都可以通过网络分解在局部模型的Poly(εn，1/ε)轮中用(1±ε)个因子逼近[Ghaffari，Kuhn，and Maus，STEC2018]。然而，这些方法需要发送无限大小的消息，因此它们不会扩展到更现实的拥塞模型，该模型将消息大小限制为O(Logn)比特。例如，尽管对分布式匹配问题进行了大量的研究，但在拥塞模型中，(1-ε)-近似的最大加权匹配能否在Poly(logn，1/ε)轮中计算仍然是一个主要的未解决问题。在该文中，我们提出了一个通用的框架来获得许多组合优化问题的Poly(logn，1/ε)-轮(1±ε)-近似算法，包括最大加权匹配、最大独立集和相关聚类。这类图涵盖了许多已被研究的稀疏网络类，包括平面图、有界亏格图和有界树宽图。此外，我们还证明了该框架可用于给出任意次闭图在不相交并下闭合的分布式属性测试算法，大大推广了[Levi，Medina，and Ron，PODC 2018&Distributed Computing 2021]中针对平面性的分布式属性测试算法。我们证明了除固定的子项外的任何图都有小的边分隔符。利用这一结果，我们证明了在扩展器分解中每个簇中存在一个高次顶点，这使得簇的整个图拓扑可以被路由到一个顶点。类似于在局部模型中使用网络分解，顶点将能够在由簇诱导的子图上执行任何局部计算，并在簇上广播结果。
Many combinatorial optimization problems, including maximum weighted matching and maximum independent set, can be approximated within (1 ± ε) factors in poly(log n, 1/ε) rounds in the LOCAL model via network decompositions [Ghaffari, Kuhn, and Maus, STOC 2018]. These approaches, however, require sending messages of unlimited size, so they do not extend to the more realistic CONGEST model, which restricts the message size to be O(log n) bits. For example, despite the long line of research devoted to the distributed matching problem, it still remains a major open problem whether an (1-ε)-approximate maximum weighted matching can be computed in poly(log n, 1/ε) rounds in the CONGEST model.In this paper, we develop a generic framework for obtaining poly(log n, 1/ε)-round (1 ± ε)-approximation algorithms for many combinatorial optimization problems, including maximum weighted matching, maximum independent set, and correlation clustering, in graphs excluding a fixed minor in the CONGEST model. This class of graphs covers many sparse network classes that have been studied in the literature, including planar graphs, bounded-genus graphs, and bounded-treewidth graphs.Furthermore, we show that our framework can be applied to give an efficient distributed property testing algorithm for an arbitrary minor-closed graph property that is closed under taking disjoint union, significantly generalizing the previous distributed property testing algorithm for planarity in [Levi, Medina, and Ron, PODC 2018 & Distributed Computing 2021].Our framework uses distributed expander decomposition algorithms [Chang and Saranurak, FOCS 2020] to decompose the graph into clusters of high conductance. We show that any graph excluding a fixed minor admits small edge separators. Using this result, we show the existence of a high-degree vertex in each cluster in an expander decomposition, which allows the entire graph topology of the cluster to be routed to a vertex. Similar to the use of network decompositions in the LOCAL model, the vertex will be able to perform any local computation on the subgraph induced by the cluster and broadcast the result over the cluster.
登录
查看更多内容
近乎最佳时间的分布式平面可达性
DOI：
--
发表时间：
2020
期刊：
International Symposium on Distributed Computing
影响因子：
--
作者：
M. Parter
通讯作者：
M. Parter
两种本地模型中的最佳：集中式本地算法和分布式本地算法
影响因子：
1
作者：
G. Even;Moti Medina;D. Ron
通讯作者：
D. Ron
具有次多项式最坏情况更新时间的动态最小生成森林
DOI：
10.1109/focs.2017.92
发表时间：
2017
期刊：
2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)
影响因子：
--
作者：
Danupon Nanongkai;Thatchaphol Saranurak;Christian Wulff
通讯作者：
Christian Wulff
轮次和消息最优分布式图算法
DOI：
10.1145/3212734.3212737
发表时间：
2018
期刊：
ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing
影响因子：
--
作者：
Haeupler, Bernhard;Hershkowitz, D. Ellis;Wajc, David
通讯作者：
Wajc, David
DOI：
--
发表时间：
2021
期刊：
Proceedings of the 32nd International Symposium on Algorithms and Computation (ISAAC 2021)
影响因子：
--
作者：
尾家 慶彦;三分一 史和;越久 仁敬;Hirrlinger Johannes;Swen H?lsmann;François Le Gall and Masayuki Miyamoto
通讯作者：
François Le Gall and Masayuki Miyamoto