A rich line of work has been addressing the computational complexity of locally checkable labelings (LCLs), illustrating the landscape of possible complexities. In this paper, we study the landscape of LCL complexities under bandwidth restrictions. Our main results are twofold. First, we show that on trees, the CONGEST complexity of an LCL problem is asymptotically equal to its complexity in the LOCAL model. An analog statement for general (non-LCL) problems is known to be false. Second, we show that for general graphs this equivalence does not hold, by providing an LCL problem for which we show that it can be solved in $O(\log n)$ rounds in the LOCAL model, but requires $\tilde{\Omega}(n^{1/2})$ rounds in the CONGEST model.
翻译:处理本地可核对标签(LCLs)的计算复杂性是一项内容丰富的工作,说明了可能的复杂情况。在本文中,我们研究了在带宽限制下LCL复杂性的景观。我们的主要结果有两个。首先,我们表明,在树木上,LCL问题的CONEST复杂性与LOCOL模型的复杂程度无异。一般(非LLLL)问题的模拟说明已知是虚假的。第二,我们通过提供一个LCL问题,表明LCL可以用LOCAL模型的美元(log n)解决,但在CONEST模型中则需要$(tilde\Omega}(n ⁇ 1/2})美元。