Local Mending

Structural Information and Communication Complexity - 29th International Colloquium, SIROCCO 2022, Proceedings, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Volume 13298 LNCS

Abstract

In this work we introduce the graph-theoretic notion of mendability: for each locally checkable graph problem we can define its mending radius, which captures the idea of how far one needs to modify a partial solution in order to “patch a hole.” We explore how mendability is connected to the existence of efficient algorithms, especially in distributed, parallel, and fault-tolerant settings. It is easy to see that O(1)-mendable problems are also solvable in O(log∗n) rounds in the LOCAL model of distributed computing. One of the surprises is that in paths and cycles, a converse also holds in the following sense: if a problem Π can be solved in O(log∗n), there is always a restriction Π′⊆ Π that is still efficiently solvable but that is also O(1)-mendable. We also explore the structure of the landscape of mendability. For example, we show that in trees, the mending radius of any locally checkable problem is O(1), Θ(log n), or Θ(n), while in general graphs the structure is much more diverse.

Description

| openaire: EC/H2020/840605/EU//CoCoNat Funding Information: Acknowledgements. This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 840605. This work was supported in part by the Academy of Finland, Grants 314888 and 333837. The authors would also like to thank David Harris, Neven Villani, and the anonymous reviewers for their very helpful comments and feedback on previous versions of this work. Publisher Copyright: © 2022, Springer Nature Switzerland AG.

Keywords

Distributed algorithms, Dynamic algorithms, Fault tolerance, LCL problems, Mendability, Parallel algorithms

DOI

10.1007/978-3-031-09993-9_1

Citation

Balliu, A, Hirvonen, J, Melnyk, D, Olivetti, D, Rybicki, J & Suomela, J 2022, Local Mending . in M Parter (ed.), Structural Information and Communication Complexity - 29th International Colloquium, SIROCCO 2022, Proceedings . Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13298 LNCS, Springer, pp. 1-20, International Colloquium on Structural Information and Communication Complexity, Paderborn, Germany, 27/06/2022 . https://doi.org/10.1007/978-3-031-09993-9_1

Permanent link to this item

https://urn.fi/URN:NBN:fi:aalto-202209075342

Collections

[article-cris] Perustieteiden korkeakoulu / SCI

Show all metadata

Local Mending

Access rights

URL

Journal Title

Journal ISSN

Volume Title

Authors

Date

Department

Major/Subject

Mcode

Degree programme

Language

Pages

Series