SIROCCO 2021 · 28th International Colloquium on Structural Information and Communication Complexity, Wrocław, Poland, June–July 2021

The *locality* of a graph problem is the smallest distance $T$ such that each node can choose its own part of the solution based on its radius-$T$ neighborhood. In many settings, a graph problem can be solved efficiently with a distributed or parallel algorithm if and only if it has a small locality.

In this work we seek to *automate* the study of solvability and locality: given the description of a graph problem $\Pi$, we would like to determine if $\Pi$ is solvable and what is the asymptotic locality of $\Pi$ as a function of the size of the graph. Put otherwise, we seek to automatically *synthesize* efficient distributed and parallel algorithms for solving $\Pi$.

We focus on *locally checkable* graph problems; these are problems in which a solution is globally feasible if it looks feasible in all constant-radius neighborhoods. Prior work on such problems has brought primarily bad news: questions related to locality are undecidable in general, and even if we focus on the case of *labeled* paths and cycles, determining locality is PSPACE-hard (Balliu et al., PODC 2019).

We complement prior negative results with efficient algorithms for the cases of *unlabeled* paths and cycles and, as an extension, for rooted trees. We study locally checkable graph problems from an automata-theoretic perspective by representing a locally checkable problem $\Pi$ as a *nondeterministic finite automaton* $\mathcal{M}$ over a *unary alphabet*. We identify polynomial-time-computable properties of the automaton $\mathcal{M}$ that near-completely capture the solvability and locality of $\Pi$ in cycles and paths, with the exception of one specific case that is co-NP-complete.