License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2023.7
URN: urn:nbn:de:0030-drops-191330
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/19133/
Balliu, Alkida ;
Brandt, Sebastian ;
Kuhn, Fabian ;
Olivetti, Dennis ;
Schmid, Gustav
On the Node-Averaged Complexity of Locally Checkable Problems on Trees
Abstract
Over the past decade, a long line of research has investigated the distributed complexity landscape of locally checkable labeling (LCL) problems on bounded-degree graphs, culminating in an almost-complete classification on general graphs and a complete classification on trees. The latter states that, on bounded-degree trees, any LCL problem has deterministic worst-case time complexity O(1), Θ(log^* n), Θ(log n), or Θ(n^{1/k}) for some positive integer k, and all of those complexity classes are nonempty. Moreover, randomness helps only for (some) problems with deterministic worst-case complexity Θ(log n), and if randomness helps (asymptotically), then it helps exponentially.
In this work, we study how many distributed rounds are needed on average per node in order to solve an LCL problem on trees. We obtain a partial classification of the deterministic node-averaged complexity landscape for LCL problems. As our main result, we show that every problem with worst-case round complexity O(log n) has deterministic node-averaged complexity O(log^* n). We further establish bounds on the node-averaged complexity of problems with worst-case complexity Θ(n^{1/k}): we show that all these problems have node-averaged complexity Ω̃(n^{1 / (2^k - 1)}), and that this lower bound is tight for some problems.
BibTeX - Entry
@InProceedings{balliu_et_al:LIPIcs.DISC.2023.7,
author = {Balliu, Alkida and Brandt, Sebastian and Kuhn, Fabian and Olivetti, Dennis and Schmid, Gustav},
title = {{On the Node-Averaged Complexity of Locally Checkable Problems on Trees}},
booktitle = {37th International Symposium on Distributed Computing (DISC 2023)},
pages = {7:1--7:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-301-0},
ISSN = {1868-8969},
year = {2023},
volume = {281},
editor = {Oshman, Rotem},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/19133},
URN = {urn:nbn:de:0030-drops-191330},
doi = {10.4230/LIPIcs.DISC.2023.7},
annote = {Keywords: distributed graph algorithms, locally checkable labelings, node-averaged complexity, trees}
}
|
Keywords: |
|
distributed graph algorithms, locally checkable labelings, node-averaged complexity, trees |
|
Collection: |
|
37th International Symposium on Distributed Computing (DISC 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
05.10.2023 |
