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
In this work we seek to automate the study of solvability and locality: given the description of a graph problem
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
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