LCL problems on grids
| Autor: | Christopher Purcell, Juho Hirvonen, Joel Rybicki, Przemyslaw Uznanski, Patric R. J. Östergård, Sebastian Brandt, Tuomo Lempiäinen, Jukka Suomela, Janne H. Korhonen |
|---|---|
| Přispěvatelé: | Biosciences, Centre of Excellence in Metapopulation Research |
| Rok vydání: | 2017 |
| Předmět: |
Vertex (graph theory)
FOS: Computer and information sciences Computational complexity theory education 0102 computer and information sciences 02 engineering and technology Computational Complexity (cs.CC) 01 natural sciences Combinatorics TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY Computer Science - Data Structures and Algorithms 0202 electrical engineering electronic engineering information engineering Complexity class LCL problems Data Structures and Algorithms (cs.DS) Mathematics ta113 Discrete mathematics Algorithm synthesis Model of computation LOCAL model Grid 113 Computer and information sciences Undecidable problem Computational complexity Computer Science - Computational Complexity Computer Science - Distributed Parallel and Cluster Computing 010201 computation theory & mathematics Graph colouring Distributed algorithms 020201 artificial intelligence & image processing Maximal independent set Distributed Parallel and Cluster Computing (cs.DC) Constant (mathematics) MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | PODC |
| DOI: | 10.48550/arxiv.1702.05456 |
| Popis: | 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(\log^* 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(\log^* n)$, and $\Theta(n)$. However, given an LCL problem it is undecidable whether its complexity is $\Theta(\log^* n)$ or $\Theta(n)$ in 2-dimensional grids. Nevertheless, if we correctly guess that the complexity of a problem is $\Theta(\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' \circ S_k$, where $A'$ 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|