Deterministic Distributed Edge-Coloring via Hypergraph Maximal Matching
Deterministic Distributed Edge-Coloring via Hypergraph Maximal Matching
复制标题
通过超图最大匹配确定性分布式边缘着色
DOI：
10.1109/focs.2017.25
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
F. Kuhn
中科院分区：
文献类型：
--
作者：
Manuela Fischer;M. Ghaffari;F. Kuhn
我们提出了一个确定性的分布式算法，计算（2 - 1）-边染色，甚至列表边染色，在任何n-节点图的最大程度，在O（log^8 log n）轮。这回答了20世纪80年代后期分布式图算法的一个长期存在的开放问题，该问题要求一个多线程时间算法。参见，例如，Barenboim和Elkin的分布式图着色书中的开放问题4。之前最好的轮复杂度是Panconesi和Srinivasan的2^{O（{log n}）}[STOC 92]和Fraigniaud，Heinrich和Kosowski的（{}）+ O（log^* n）[FOCS 16]。我们的确定性列表边着色的一个推论也提高了（2 - 1）-边着色到多（loglog n）轮的随机复杂性。关键的技术成分是超图最大匹配的确定性分布式算法，我们相信这将是超越这个结果的兴趣。在任意秩为r的超图中，如果每个超图的超边最多有r个顶点，且顶点数为n，最大度为n，则该算法在O（r^5 log^{6+log r } log n）轮内计算出最大匹配.特别地，我们得到了一个多对数时间确定性的分布式最大独立集算法，从而回答了Barenboim和埃尔金斯书中的公开问题5，一个\big（（log/）^{O（log 1/）}\big）轮确定性算法，用于（1+）-近似最大匹配，以及一个准多对数时间确定性的分布式算法，用于定向-荫度最多\lceil（1+）\rceil，对于任何常数0，从而部分回答了Barenboim和埃尔金斯书中的公开问题10。
We present a deterministic distributed algorithm that computes a (2δ-1)-edge-coloring, or even list-edge-coloring, in any n-node graph with maximum degree δ, in O(log^8 δ ⋅ log n) rounds. This answers one of the long-standing open questions of distributed graph algorithms} from the late 1980s, which asked for a polylogarithmic-time algorithm. See, e.g., Open Problem 4 in the Distributed Graph Coloring book of Barenboim and Elkin. The previous best round complexities were 2^{O(√{log n})} by Panconesi and Srinivasan [STOC92] and Õ(√{δ}) + O(log^* n) by Fraigniaud, Heinrich, and Kosowski [FOCS16]. A corollary of our deterministic list-edge-coloring also improves the randomized complexity of (2δ-1)-edge-coloring to poly(loglog n) rounds.The key technical ingredient is a deterministic distributed algorithm for hypergraph maximal matching, which we believe will be of interest beyond this result. In any hypergraph of rank r — where each hyperedge has at most r vertices — with n nodes and maximum degree δ, this algorithm computes a maximal matching in O(r^5 log^{6+log r } δ ⋅ log n) rounds.This hypergraph matching algorithm and its extensions also lead to a number of other results. In particular, we obtain a polylogarithmic-time deterministic distributed maximal independent set (MIS) algorithm for graphs with bounded neighborhood independence, hence answering Open Problem 5 of Barenboim and Elkins book, a \big((log δ/ε)^{O(log 1/ε)}\big)-round deterministic algorithm for (1+ε)-approximation of maximum matching, and a quasi-polylogarithmic-time deterministic distributed algorithm for orienting λ-arboricity graphs with out-degree at most \lceil (1+ε)λ \rceil, for any constant ε 0, hence partially answering Open Problem 10 of Barenboim and Elkins book.