I'm reading the article "What can be computed locally?" by Naor & Stockmeyer and I struggle to understand the definition of an LCL they gave. Here is an extract: (page 2)

An Locally Checkable Labelling (LCL) $\mathcal{L}$ consist of a positive integer $r$, a set $\Sigma$ of input labels, a set $\Gamma$ of output labels and a set $\mathcal{C}$ of of locally consistent labels. Given a graph $G$ and $\lambda: V\mapsto \Sigma \times \Gamma$, we say that $\lambda$ is $\mathcal{L}$-legal if $\forall u \in V$, there exists $(H,s) \in \mathcal{C}$ and an isomorphism $\pi$ mapping $B(u,r)$ to $H$ such that $\pi(u) = s$ and $\pi$ respect the labelling, i.e. for all label-pair $w$, equals the label pair $\pi(w)$.

Note: $(H,s)$ is a graph centered in $s$, a.k.a. $s \in H$.

I don't really understand some part of this definition, but mostly what $\mathcal{C}$ looks like. I tried to think of a simple exemple: classic vertex coloration where you don't allow to neighbors to have the same colors.

Suppose we need $c$ colors; so $\Gamma = [c]$. Clearly $r=1$ as it is sufficient for nodes to check up to their direct neighbors. Now I'm not sure what $\Sigma$ can look like; I suspect in the case of coloration it is not really needed as this problem is too simple? As for $\mathcal{C}$ my guess is that it should include the informations relative to all the vertices and their direct neighbors, but I don't see how and what $\pi$ fits in all this.

  • $\begingroup$ "I don't really understand ..." is hardly a research level question, which is what cstheory targets. $\endgroup$
    – Kai
    Aug 30, 2023 at 15:59
  • $\begingroup$ Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it's hard to tell exactly what you're asking. $\endgroup$
    – Kai
    Aug 30, 2023 at 16:00


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.