LCL problems on grids

PODC 2017 · 36th ACM Symposium on Principles of Distributed Computing, Washington, D.C., USA, July 2017

Abstract

LCLs or locally checkable labelling problems (e.g. maximal independent set, maximal matching, and vertex colouring) in the LOCAL model of computation are very well-understood in cycles (toroidal 1-dimensional grids): every problem has a complexity of $O(1)$, $\Theta(\log^* n)$, or $\Theta(n)$, and the design of optimal algorithms can be fully automated.

This work develops the complexity theory of LCL problems for toroidal 2-dimensional grids. The complexity classes are the same as in the 1-dimensional case: $O(1)$, $\Theta(\log^* n)$, and $\Theta(n)$. However, given an LCL problem it is undecidable whether its complexity is $\Theta(\log^* n)$ or $\Theta(n)$ in 2-dimensional grids.

Nevertheless, if we correctly guess that the complexity of a problem is $\Theta(\log^* n)$, we can completely automate the design of optimal algorithms. For any problem we can find an algorithm that is of a normal form $A' \circ S_k$, where $A'$ is a finite function, $S_k$ is an algorithm for finding a maximal independent set in $k$th power of the grid, and $k$ is a constant.

With the help of this technique, we study several concrete LCL problems, also in more general settings. For example, for all $d \ge 2$, we prove that:

• $d$-dimensional grids can be $k$-vertex coloured in time $O(\log^* n)$ iff $k \ge 4$,
• $d$-dimensional grids can be $k$-edge coloured in time $O(\log^* n)$ iff $k \ge 2d+1$.

The proof that $3$-colouring of $2$-dimensional grids requires $\Theta(n)$ time introduces a new topological proof technique, which can also be applied to e.g. orientation problems.

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.