CISPA
Browse
cispa_all_3762.pdf (698.56 kB)

Efficient Classification of Locally Checkable Problems in Regular Trees

Download (698.56 kB)
conference contribution
posted on 2023-11-29, 18:22 authored by Alkida Balliu, Sebastian BrandtSebastian Brandt, Yi-Jun Chang, Dennis Olivetti, Jan Studený, Jukka Suomela
We give practical, efficient algorithms that automatically determine the asymptotic distributed round complexity of a given locally checkable graph problem in the [Θ(log n), Θ(n)] region, in two settings. We present one algorithm for unrooted regular trees and another algorithm for rooted regular trees. The algorithms take the description of a locally checkable labeling problem as input, and the running time is polynomial in the size of the problem description. The algorithms decide if the problem is solvable in O(log n) rounds. If not, it is known that the complexity has to be Θ(n^{1/k}) for some k = 1, 2, ..., and in this case the algorithms also output the right value of the exponent k. In rooted trees in the O(log n) case we can then further determine the exact complexity class by using algorithms from prior work; for unrooted trees the more fine-grained classification in the O(log n) region remains an open question.

History

Preferred Citation

Alkida Balliu, Sebastian Brandt, Yi-Jun Chang, Dennis Olivetti, Jan Studený and Jukka Suomela. Efficient Classification of Locally Checkable Problems in Regular Trees. In: DISC International Symposium on Distributed Computing (DISC). 2022.

Primary Research Area

  • Algorithmic Foundations and Cryptography

Name of Conference

DISC International Symposium on Distributed Computing (DISC)

Legacy Posted Date

2022-09-09

Open Access Type

  • Gold

BibTeX

@inproceedings{cispa_all_3762, title = "Efficient Classification of Locally Checkable Problems in Regular Trees", author = "Balliu, Alkida and Brandt, Sebastian and Chang, Yi-Jun and Olivetti, Dennis and Studený, Jan and Suomela, Jukka", booktitle="{DISC International Symposium on Distributed Computing (DISC)}", year="2022", }

Usage metrics

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC