Reminder: This post contains 1917 words
· 6 min read
· by Xianbin
This post introduce the celebrated and initial work on locally checkable labeling (LCL) problems based on [1].
Motivation
We want to know what can be computed when an algorithm must satisfy the following requirement: running in constant time.
A node(processor) \(u\) running in constant time must output solely on \(N^t(u)\).
Definitions
The initial definition is very general and not easy to memorize. So, let us see an alternative definition [2].
An LCL problem \(\Pi\) is a tuple \((\Sigma_{\text{in}}, \Sigma_{\text{out}}, \mathcal{C},r)\):
- \(\Sigma_{*}\) is a set of labels of constant size.
-
\(r\) is a constant.
- \(\mathcal{C}\) is a set of pairs \((H,v)\) where \(H\) is a radius-r subgraph centered at \(v\in H\), each vertex in \(H\) is assigned an input label from \(\Sigma_{\text{in}}\) and an output label from \(\Sigma_{\text{out}}\).
We say that we solve a problem \(\Pi\) if in a graph where each node-edge \((v, e)\) pair is labeled with a label in \(\Sigma_{\text{in}}\), and we need to assign a label in \(\Sigma_{\text{out}}\) to each node-edge pair such that every \(N^r(v)\) for each node \(v\) is isomorphic to a labeled graph contained in \(\mathcal{C}\). Put it in another word, the output labeling \(\phi_{\text{out}}\) should be locally consistent for a vertex \(v\in V\) if its \(N^r(v)\) is an allowed configuration in \(\mathcal{C}\) under the given \(\Sigma_{\text{in}}\) and \(\Sigma_{\text{out}}\).
Then, we say the output labeling \(\phi_{\text{out}}\) is legal.
Some Results
\(\textbf{Theorem 1}\) [informal]. If a LCL problem has a local randomized algorithm, then it has a local deterministic algorithm.
It means that in some situations, randomization does not help!
\(\textbf{Theorem 2}\) [informal]. If an LCL problem has a local algorithm, then it also has an order-invariant algorithm (the algorithm only depends on the orders of IDs).
Reference
[1]. Naor, M. and Stockmeyer, L., 1993, June. What can be computed locally?. In Proceedings of the twenty-fifth annual ACM symposium on Theory of computing (pp. 184-193).
[2]. Balliu, A., Censor-Hillel, K., Maus, Y., Olivetti, D. and Suomela, J., 2021, October. Locally Checkable Labelings with Small Messages. In 35th International Symposium on Distributed Computing.