We prove several new tight distributed lower bounds for classic symmetry breaking graph problems. As a basic tool, we first provide a new insightful proof that any deterministic distributed algorithm that computes a $\Delta$-coloring on $\Delta$-regular trees requires $\Omega(\log_\Delta n)$ rounds and any randomized algorithm requires $\Omega(\log_\Delta\log n)$ rounds. We prove this result by showing that a natural relaxation of the $\Delta$-coloring problem is a fixed point in the round elimination framework. As a first application, we show that our $\Delta$-coloring lower bound proof directly extends to arbdefective colorings. We exactly characterize which variants of the arbdefective coloring problem are "easy", and which of them instead are "hard". As a second application, which we see as our main contribution, we use the structure of the fixed point as a building block to prove lower bounds as a function of $\Delta$ for a large class of distributed symmetry breaking problems. For example, we obtain a tight lower bound for the fundamental problem of computing a $(2,\beta)$-ruling set. This is an exponential improvement over the best existing lower bound for the problem, which was proven in [FOCS '20]. Our lower bound even applies to a much more general family of problems that allows for almost arbitrary combinations of natural constraints from coloring problems, orientation problems, and independent set problems, and provides a single unified proof for known and new lower bound results for these types of problems. Our lower bounds as a function of $\Delta$ also imply lower bounds as a function of $n$. We obtain, for example, that maximal independent set, on trees, requires $\Omega(\log n / \log \log n)$ rounds for deterministic algorithms, which is tight.
翻译:我们为经典的对称断面图形问题证明了一些新的紧分布下拉线。 作为基本工具, 我们首先提供一个新的有洞察力的证明, 任何计算$\ Delta$ 的确定性分布算法, 在$\ Delta$- 普通树上计算 $\ Delta$ 彩色的确定性分布算法, 需要$\ omega( log\\ Delta\ delta n) 圆盘, 而任何随机化算法需要$\ omega (log\\ delta\ log n) 圆盘。 我们通过显示$\ Deltal- 彩色问题的自然缓和, 我们精确地辨明, 硬彩色的变色问题是“ 难 ” 。 作为第二个应用程序, 我们所看到的主要贡献, 我们用固定点的结构来证明, 更低的框框块是 $\ delta$ 的固定值, 几乎是直径直线值的任意值, 直径直径直径直到 的直径直径直径直径直的 。