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.

Yet what we are seeing more and more often is that there are LCL problems with unexpected, counterintuitive properties, that we have never seen in “natural” local graph problems, for example:

• There is an LCL problem that admits a distributed quantum advantage [SODA 2026].
• There is an LCL problem that benefits from shared randomness and from shared quantum state [ICALP 2026].
• There is an LCL problem whose complexity in the LOCAL model depends on whether state transitions are restricted to computable functions.
• We can construct LCL problems with unnatural round complexities such as $\Theta(\log^{123.45} n)$ and $\Theta(n^{0.12345})$ [STOC 2018].

Furthermore, many questions related to the distributed complexity of LCL problems are undecidable [STOC 1993, PODC 2017]. Overall, the LCL problems seem to be a poor proxy for the family of natural local graph problems. With large volumes of research on LCL problems, the following questions are getting ever more pressing: Are we studying the right problem family? Maybe the above counterintuitive features are mere artifacts of the specific definition of LCLs introduced by Naor and Stockmeyer, and they disappear if we slightly restrict the family of LCL problems?

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. the existence of short cycles. We show that one can translate between the two formalisms (there are local reductions in both directions that only need access to a symmetry-breaking oracle, and hence the overhead is at most an additive $O(\log^* n)$ rounds in the LOCAL model). In particular, all counterintuitive properties listed above hold also for restricted LCLs.