## 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′·S_{k}, where A′ is a finite function, S_{k} 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 language | English |
---|---|

Title of host publication | PODC 2017 - Proceedings of the ACM Symposium on Principles of Distributed Computing |

Publisher | ACM |

Pages | 101-110 |

Number of pages | 10 |

Volume | Part F129314 |

ISBN (Electronic) | 9781450349925 |

DOIs | |

Publication status | Published - 26 Jul 2017 |

MoE publication type | A4 Article in a conference publication |

Event | ACM Symposium on Principles of Distributed Computing - Washington, United States Duration: 25 Jul 2017 → 27 Jul 2017 Conference number: 36 |

### Conference

Conference | ACM Symposium on Principles of Distributed Computing |
---|---|

Abbreviated title | PODC |

Country/Territory | United States |

City | Washington |

Period | 25/07/2017 → 27/07/2017 |

## Keywords

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