LCL problems on grids

DOI10.1145/3087801.3087833MaRDI QIDQ5368949zbMATH OpenOpenAlexFDO

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)

Full work available at URL https://arxiv.org/abs/1702.05456, http://hdl.handle.net/10138/310060

zbMATH Keywords

algorithm synthesiscomputational complexitydistributed algorithmsgraph colouringLCL problemslocal model

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)

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.

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

Cited in

(22)

• Almost global problems in the LOCAL model
• Local mending
• Distributed algorithms for fractional coloring
• Distributed graph problems through an automata-theoretic Lens
• Probabilistic constructions in continuous combinatorics and a bridge to distributed algorithms
• Distributed graph problems through an automata-theoretic lens
• Constant space and non-constant time in distributed computing
• A time hierarchy theorem for the LOCAL model
• Almost global problems in the LOCAL model
• Distributed recoloring
• 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
• Algorithms and complexity for counting configurations in Steiner triple systems
• Classification of distributed binary labeling problems
• The complexity landscape of distributed locally checkable problems on trees
• Brief announcement: Distributed graph problems through an automata-theoretic lens
• Complexity of finite Borel asymptotic dimension
• Exponential speedup over locality in \textsf{MPC} with optimal memory
• The distributed complexity of locally checkable labeling problems beyond paths and trees
• Completing the node-averaged complexity landscape of LCLs on trees
• A tight lower bound for 3-coloring grids in the online-LOCAL model
• Shared randomness helps with local distributed problems

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)