Online Edge Coloring Algorithms via the Nibble Method
Online Edge Coloring Algorithms via the Nibble Method
复制标题
通过 Nibble 方法的在线边缘着色算法
DOI：
10.1137/1.9781611976465.168
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
David Wajc
中科院分区：
文献类型：
--
作者：
Sayan Bhattacharya;F. Grandoni;David Wajc
大约三十年前，Bar-Noy、Motwani 和 Naor [IPL'92] 推测，对于最大度数 $\Delta=\omega(\log n)$ 的 $n$ 节点图，存在在线 $(1+o(1))\Delta$ 边缘着色算法。尽管 Cohen 等人最近在 \emph{单边顶点到达}下的二部图证明了这一猜想，但总体上仍然是开放的。~[FOCS'19]。同样，我们在广泛研究的在线模型松弛下研究边缘着色。
我们的主要结果是 \emph{random-order} 在线模型。对于该模型，已知结果未达到 Bar-Noy 等人的猜想，无论是在程度范围 [Aggarwal 等人~FOCS'03] 上，还是在使用的颜色数量上 [Bahmani 等人~SODA'10]。我们实现了两全其美，从而解决了 Bar-Noy 等人对该模型的肯定猜想。
我们的第二个结果是具有 \emph{recourse} 的对抗性在线（和动态）模型。 Duan 等人最近的算法~[SODA'19] 产生了一个带有 poly$(\log n/\epsilon)$ 资源的 $(1+\epsilon)\Delta$-边缘着色。我们使用 poly$(1/\epsilon)$ 资源实现了相同的目的，从而消除了对 $n$ 的所有依赖。
我们结果的基础是一种常见的离线算法，我们展示了如何在这两种在线模型中实现该算法。我们的算法基于 Rodl Nibble 方法，是 Dubhashi 等人的分布式算法的改编版~[TCS'98]。事实证明，蚕食方法对于分布式边缘着色是成功的。我们在在线算法的背景下展示了它的有用性。
Nearly thirty years ago, Bar-Noy, Motwani and Naor [IPL'92] conjectured that an online $(1+o(1))\Delta$-edge-coloring algorithm exists for $n$-node graphs of maximum degree $\Delta=\omega(\log n)$. This conjecture remains open in general, though it was recently proven for bipartite graphs under \emph{one-sided vertex arrivals} by Cohen et al.~[FOCS'19]. In a similar vein, we study edge coloring under widely-studied relaxations of the online model.
Our main result is in the \emph{random-order} online model. For this model, known results fall short of the Bar-Noy et al.~conjecture, either in the degree bound [Aggarwal et al.~FOCS'03], or number of colors used [Bahmani et al.~SODA'10]. We achieve the best of both worlds, thus resolving the Bar-Noy et al.~conjecture in the affirmative for this model.
Our second result is in the adversarial online (and dynamic) model with \emph{recourse}. A recent algorithm of Duan et al.~[SODA'19] yields a $(1+\epsilon)\Delta$-edge-coloring with poly$(\log n/\epsilon)$ recourse. We achieve the same with poly$(1/\epsilon)$ recourse, thus removing all dependence on $n$.
Underlying our results is one common offline algorithm, which we show how to implement in these two online models. Our algorithm, based on the Rodl Nibble Method, is an adaptation of the distributed algorithm of Dubhashi et al.~[TCS'98]. The Nibble Method has proven successful for distributed edge coloring. We display its usefulness in the context of online algorithms.