跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2608.02386 · v3

Greedy-Like Defective Coloring: Distributed Algorithms and Applications

首次提交 2026-08-03 23:29
版本更新 2026-11-07 00:35
雷达观测 2026-11-09 13:22
arXiv ↗PDF ↗

摘要

A dd-defective cc-coloring of a graph G=(V,E)G=(V,E) is a coloring of the nodes VV with cc colors such that every node has at most dd neighbors of the same color. Distributed algorithms for computing different variants of defective coloring are at the core of most deterministic state-of-the-art distributed coloring algorithms, and they are also an important tool in many other distributed graph algorithms. In several cases, the overall complexity could be improved if some version of defective coloring could be solved more efficiently. Barenboim and Elkin [STOC '09] introduced a two-pass greedy algorithm that uses p2p^2 colors with defect ⌊Δ/p⌋\lfloor Δ/p\rfloor in O(Δ+log⁡∗n)O(Δ+\log^{\ast} n) rounds. This remains the best defect/color tradeoff for O(log⁡∗n)O(\log^{\ast} n)-time algorithms in bounded-degree graphs. This paper expands the capabilities of this two-pass algorithm. First, we generalize it to the \emph{list defective coloring} problem (Fuchs and Kuhn, [DISC '23]). Consequently, we obtain an alternative algorithm for computing a proper (Δ+1)(Δ+1)-coloring in O~(Δ)+O(log⁡∗n)\tilde{O}(\sqrtΔ) + O(\log^{\ast} n) rounds in the CONGEST model. Second, we analyze a generalized two-pass algorithm for standard defective colorings. We prove that if the number of colors cc is not a perfect square, we can improve the state-of-the-art defect for distributed cc-colorings by a constant factor in most cases. However, we also prove a limitation: for any c≥1c\geq 1, this generalized algorithm cannot achieve a cc-coloring with defect below (1−o(1))⋅Δ/c(1-o(1))\cdotΔ/\sqrt{c}.

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

本站首次收录为 v3,暂无更早版本可对照。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v3 · 2026-11-07 00:35 · 最新观测版本

Greedy-Like Defective Coloring: Distributed Algorithms and Applications

A dd-defective cc-coloring of a graph G=(V,E)G=(V,E) is a coloring of the nodes VV with cc colors such that every node has at most dd neighbors of the same color. Distributed algorithms for computing different variants of defective coloring are at the core of most deterministic state-of-the-art distributed coloring algorithms, and they are also an important tool in many other distributed graph algorithms. In several cases, the overall complexity could be improved if some version of defective coloring could be solved more efficiently. Barenboim and Elkin [STOC '09] introduced a two-pass greedy algorithm that uses p2p^2 colors with defect ⌊Δ/p⌋\lfloor Δ/p\rfloor in O(Δ+log⁡∗n)O(Δ+\log^{\ast} n) rounds. This remains the best defect/color tradeoff for O(log⁡∗n)O(\log^{\ast} n)-time algorithms in bounded-degree graphs. This paper expands the capabilities of this two-pass algorithm. First, we generalize it to the \emph{list defective coloring} problem (Fuchs and Kuhn, [DISC '23]). Consequently, we obtain an alternative algorithm for computing a proper (Δ+1)(Δ+1)-coloring in O~(Δ)+O(log⁡∗n)\tilde{O}(\sqrtΔ) + O(\log^{\ast} n) rounds in the CONGEST model. Second, we analyze a generalized two-pass algorithm for standard defective colorings. We prove that if the number of colors cc is not a perfect square, we can improve the state-of-the-art defect for distributed cc-colorings by a constant factor in most cases. However, we also prove a limitation: for any c≥1c\geq 1, this generalized algorithm cannot achieve a cc-coloring with defect below (1−o(1))⋅Δ/c(1-o(1))\cdotΔ/\sqrt{c}.

查看此版本解读 →查看此版本原文 ↗