SIROCCO 2021 · 28th International Colloquium on Structural Information and Communication Complexity, online, June–July 2021 · doi:10.1007/978-3-030-79527-6_3

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.

Tomasz Jurdziński and Stefan Schmid (Eds.): *Structural Information and Communication Complexity, 28th International Colloquium, SIROCCO 2021, Wrocław, Poland, June 28 – July 1, 2021, Proceedings*, volume 12810 of *Lecture Notes in Computer Science*, pages 31–49, Springer, Berlin, 2021

ISBN 978-3-030-79527-6

- Yi-Jun Chang, Jan Studený, and Jukka Suomela: Distributed graph problems through an automata-theoretic lens ·
*Theoretical Computer Science*, to appear