标题： 关于分布式边着色和定向问题的复杂性 显示英文标题

标题： On the Complexity of Distributed Edge Coloring and Orientation Problems

摘要： 在 LOCAL 模型中理解随机性在解决局部可检查标签 (LCL) 问题中的作用，一直是近年来分布式图算法研究的首要任务之一。 对于有界度图中的 LCL 问题，已知随机性不能比多项式更有效，除了一个例外情况：如果某个 LCL 问题的确定性复杂度在$\Omega(\log n)$中，而其随机复杂度在$o(\log n)$中，则其随机复杂度保证在$poly(\log \log n)$中。 然而，关于确定性复杂度为$\Omega(\log n)$的\emph{哪个}问题是否可以使用随机化指数级更快地解决的基本问题仍然悬而未决。 我们通过研究一种简单但自然的 LCL 问题类来朝着回答这个问题迈出一步：所谓的度分裂问题。 这些问题有两种类型：边需要被染成$2$种颜色的着色问题，以及每条边需要被定向的方向问题。 对于$\Delta$-正则图（其中$\Delta=O(1)$），我们得到以下结果。 - 我们给出了所有问题的随机复杂性的精确描述，这些问题需要将边用两种颜色，比如红色和蓝色进行着色，并且具有确定性复杂度$O(\log n)$。 - 对于边定向问题，我们给出了具有随机复杂度$\Omega(\log n)$的问题和具有随机复杂度$poly\log\log n$的问题的部分描述。 虽然我们的结果在$\Delta$-正则情况下最清晰，但我们的算法自然可以推广到最大度为$\Delta$的一般图中任意度数的节点$d<\Delta$。 显示英文摘要

摘要： Understanding the role of randomness when solving locally checkable labeling (LCL) problems in the LOCAL model has been one of the top priorities in the research on distributed graph algorithms in recent years. For LCL problems in bounded-degree graphs, it is known that randomness cannot help more than polynomially, except in one case: if the deterministic complexity of an LCL problem is in $\Omega(\log n)$ and its randomized complexity is in $o(\log n)$, then the randomized complexity is guaranteed to be $poly(\log \log n)$. However, the fundamental question of \emph{which} problems with a deterministic complexity of $\Omega(\log n)$ can be solved exponentially faster using randomization still remains wide open. We make a step towards answering this question by studying a simple, but natural class of LCL problems: so-called degree splitting problems. These problems come in two varieties: coloring problems where the edges of a graph have to be colored with $2$ colors and orientation problems where each edge needs to be oriented. For $\Delta$-regular graphs (where $\Delta=O(1)$), we obtain the following results. - We gave an exact characterization of the randomized complexity of all problems where the edges need to be colored with two colors, say red and blue, and which have a deterministic complexity of $O(\log n)$. - For edge orientation problems, we give a partial characterization of the problems that have a randomized complexity of $\Omega(\log n)$ and the problems that have a randomized complexity of $poly\log\log n$. While our results are cleanest to state for the $\Delta$-regular case, all our algorithms naturally generalize to nodes of any degree $d<\Delta$ in general graphs of maximum degree $\Delta$.