LCL problems on grids

DOI10.1145/3087801.3087833zbMATH Open1380.68218arXiv1702.05456OpenAlexW2593376981MaRDI QIDQ5368949FDOQ5368949

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

Publication date: 11 October 2017

Published in: Proceedings of the ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

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)$, $Theta(lo{g}^{\ast }n)$, or $Theta(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)$, $Theta(lo{g}^{\ast }n)$, and $Theta(n)$. However, given an LCL problem it is undecidable whether its complexity is $Theta(lo{g}^{\ast }n)$ or $Theta(n)$ in 2-dimensional grids. Nevertheless, if we correctly guess that the complexity of a problem is $Theta(lo{g}^{\ast }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^{\prime }circ{S}_k$, where $A^{\prime }$ is a finite function, $S_k$ is an algorithm for finding a maximal independent set in $k$th 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.

Full work available at URL: https://arxiv.org/abs/1702.05456

Recommendations

• What Can be Computed Locally?
• Almost global problems in the LOCAL model
• New classes of distributed time complexity
• Almost global problems in the LOCAL model
• A time hierarchy theorem for the LOCAL model

zbMATH Keywords

computational complexitydistributed algorithmsgraph colouringalgorithm synthesislocal modelLCL problems

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Cited In (16)

• The complexity landscape of distributed locally checkable problems on trees
• Algorithms and complexity for counting configurations in Steiner triple systems
• Distributed algorithms for fractional coloring
• Constant space and non-constant time in distributed computing
• Local problems on grids from the perspective of distributed algorithms, finitary factors, and descriptive combinatorics
• Distributed algorithms, the Lovász local lemma, and descriptive combinatorics
• Classification of distributed binary labeling problems
• Almost global problems in the LOCAL model
• Distributed graph problems through an automata-theoretic Lens
• Distributed recoloring
• Distributed graph problems through an automata-theoretic lens
• Probabilistic constructions in continuous combinatorics and a bridge to distributed algorithms
• A time hierarchy theorem for the LOCAL model
• Brief announcement: Distributed graph problems through an automata-theoretic lens
• Almost global problems in the LOCAL model
• Local mending

This page was built for publication: LCL problems on grids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5368949)