Locality of Graph Problems in Directed Toroidic Grids

Locally checkable labeling problems in the LOCAL model of distributed computation are known to have only three distinct complexity classes when the attention is restricted to problems on toroidic grids only: trivial with time complexity Θ(1), local with time complexity Θ(log∗ n) and global with time complexity Θ(n). Prior work shows that problems belonging to the trivial class are easy to recognize, but that local and global labeling problems are undecidable to separate. However, a method called algorithm synthesis exists for creating an asymptotically optimal normal-form algorithm for any locally checkable labeling problem with a time complexity of Θ(log∗ n). This process, when automated, can be used to process vast amounts of suitably encoded labeling problems in bulk, creating a more defined boundary for the undecidable class of local problems. As a proof-of-concept of this method, this work presents a new asymptotically optimal algorithm for a relaxed form of 3-coloring as well as methods for more general search of local problems