• Computer Science > Distributed, Parallel, and Cluster Computing [Submitted on 20 Feb 2026] Title:It does not matter how you define locally checkable labelings View PDF HTML (experimental)Abstract:Locally checkable labeling problems (LCLs) form the foundation of the modern theory of distributed graph algorithms. • First introduced in the seminal paper by Naor and Stockmeyer [STOC 1993], these are graph problems that can be described by listing a finite set of valid local neighborhoods. • This seemingly simple definition strikes a careful balance between two objectives: they are a family of problems that is broad enough so that it captures numerous problems that are of interest to researchers working in this field, yet restrictive enough so that it is possible to prove strong theorems that hold for all LCL problems. • In particular, the distributed complexity landscape of LCL problems is now very well understood. • In this work we show that the family of LCL problems is extremely robust to variations. • We present a very restricted family of locally checkable problems (essentially, the “node-edge checkable” formalism familiar from round elimination, restricted to regular unlabeled graphs); most importantly, such problems cannot directly refer to e.g.
Article Summaries:
- Researchers have shown that the class of locally checkable labeling (LCL) problems-central to distributed graph algorithms-remains essentially unchanged under a surprisingly restrictive reformulation. By defining a new “node‑edge checkable” family that cannot directly reference features such as short cycles, the authors prove that any LCL can be translated into this restricted form and back. The conversions use only local reductions that rely on a symmetry‑breaking oracle, adding at most an (O(\log^* n)) overhead in the standard LOCAL model. This result underscores the robustness of the LCL framework and confirms that the well‑understood complexity landscape of LCLs is preserved across equivalent definitions.
Sources: