*Theoretical Computer Science* · volume 951, article 113710, 2023 · doi:10.1016/j.tcs.2023.113710

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 coNP-complete.

- Yi-Jun Chang, Jan Studený, and Jukka Suomela: Distributed graph problems through an automata-theoretic lens · SIROCCO 2021