LCL problems on grids
Download
No fulltext has been uploaded. References only!
Conference Paper
| Published
| English
Author
Brandt, Sebastian;
Hirvonen, Juho;
Korhonen, Janne H.;
Lempiäinen, Tuomo;
Östergård, Patric R.J.;
Purcell, Christopher;
Rybicki, JoelISTA
;
Suomela, Jukka;
Uznański, Przemysław

Abstract
LCLs or locally checkable labelling problems (e.g. maximal independent set, maximal matching, and vertex colouring) in the LOCAL model of computation are very well-understood in cycles (toroidal 1-dimensional grids): every problem has a complexity of O(1), Θ(log* n), or Θ(n), and the design of optimal algorithms can be fully automated. This work develops the complexity theory of LCL problems for toroidal 2-dimensional grids. The complexity classes are the same as in the 1-dimensional case: O(1), Θ(log* n), and Θ(n). However, given an LCL problem it is undecidable whether its complexity is Θ(log* n) or Θ(n) in 2-dimensional grids.
Nevertheless, if we correctly guess that the complexity of a problem is Θ(log* n), we can completely automate the design of optimal algorithms. For any problem we can find an algorithm that is of a normal form A' o Sk, where A' is a finite function, Sk is an algorithm for finding a maximal independent set in kth power of the grid, and k is a constant.
Finally, partially with the help of automated design tools, we classify the complexity of several concrete LCL problems related to colourings and orientations.
Publishing Year
Date Published
2017-07-01
Publisher
ACM
Page
101-110
Conference
PODC: Principles of Distributed Computing
Conference Location
Washington, DC, United States
Conference Date
2017-07-25 – 2017-07-27
ISBN
IST-REx-ID