LCL problems on grids

Sebastian Brandt, Juho Hirvonen, Janne H. Korhonen, Tuomo Lempiäinen, Patric R.J. Östergård, Christopher Purcell, Joel Rybicki, Jukka Suomela, Przemysław Uznański

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

20 Citations (Scopus)

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′·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.

Original languageEnglish
Title of host publicationPODC 2017 - Proceedings of the ACM Symposium on Principles of Distributed Computing
PublisherACM
Pages101-110
Number of pages10
VolumePart F129314
ISBN (Electronic)9781450349925
DOIs
Publication statusPublished - 26 Jul 2017
MoE publication typeA4 Article in a conference publication
EventACM Symposium on Principles of Distributed Computing - Washington, United States
Duration: 25 Jul 201727 Jul 2017
Conference number: 36

Conference

ConferenceACM Symposium on Principles of Distributed Computing
Abbreviated titlePODC
CountryUnited States
CityWashington
Period25/07/201727/07/2017

Keywords

  • Algorithm synthesis
  • Computational complexity
  • Distributed algorithms
  • Graph colouring
  • LCL problems
  • LOCAL model

Fingerprint Dive into the research topics of 'LCL problems on grids'. Together they form a unique fingerprint.

Cite this