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
IST-REx-ID

Export

Marked Publications

Open Data ISTA Research Explorer

Search this title in

Google Scholar
ISBN Search