LCL problems on grids

S. Brandt, J. Hirvonen, J.H. Korhonen, T. Lempiäinen, P.R.J. Östergård, C. Purcell, J. Rybicki, J. Suomela, P. Uznański, in:, ACM Press, 2017, pp. 101–110.

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, JoelIST Austria ; 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
Page
101-110
Conference
PODC: Principles of Distributed Computing
Conference Location
Washington, DC, United States
Conference Date
2017-07-25 – 2017-07-27
IST-REx-ID

Cite this

Brandt S, Hirvonen J, Korhonen JH, et al. LCL problems on grids. In: ACM Press; 2017:101-110. doi:10.1145/3087801.3087833
Brandt, S., Hirvonen, J., Korhonen, J. H., Lempiäinen, T., Östergård, P. R. J., Purcell, C., … Uznański, P. (2017). LCL problems on grids (pp. 101–110). Presented at the PODC: Principles of Distributed Computing, Washington, DC, United States: ACM Press. https://doi.org/10.1145/3087801.3087833
Brandt, Sebastian, Juho Hirvonen, Janne H. Korhonen, Tuomo Lempiäinen, Patric R.J. Östergård, Christopher Purcell, Joel Rybicki, Jukka Suomela, and Przemysław Uznański. “LCL Problems on Grids,” 101–10. ACM Press, 2017. https://doi.org/10.1145/3087801.3087833.
S. Brandt et al., “LCL problems on grids,” presented at the PODC: Principles of Distributed Computing, Washington, DC, United States, 2017, pp. 101–110.
Brandt S, Hirvonen J, Korhonen JH, Lempiäinen T, Östergård PRJ, Purcell C, Rybicki J, Suomela J, Uznański P. 2017. LCL problems on grids. PODC: Principles of Distributed Computing, 101–110.
Brandt, Sebastian, et al. LCL Problems on Grids. ACM Press, 2017, pp. 101–10, doi:10.1145/3087801.3087833.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar
ISBN Search