Local mending

Balliu A, Hirvonen J, Melnyk D, Olivetti D, Rybicki J, Suomela J. 2022. Local mending. International Colloquium on Structural Information and Communication Complexity. SIROCCO: Structural Information and Communication ComplexityLNCS vol. 13298, 1–20.


Conference Paper | Published | English

Scopus indexed
Author
Balliu, Alkida; Hirvonen, Juho; Melnyk, Darya; Olivetti, Dennis; Rybicki, JoelISTA ; Suomela, Jukka
Editor
Parter, Merav
Department
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), Θ(logn), or Θ(n), while in general graphs the structure is much more diverse.
Publishing Year
Date Published
2022-06-25
Proceedings Title
International Colloquium on Structural Information and Communication Complexity
Acknowledgement
This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-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.
Volume
13298
Page
1-20
Conference
SIROCCO: Structural Information and Communication Complexity
Conference Location
Paderborn, Germany
Conference Date
2022-06-27 – 2022-06-29
ISSN
eISSN
IST-REx-ID

Cite this

Balliu A, Hirvonen J, Melnyk D, Olivetti D, Rybicki J, Suomela J. Local mending. In: Parter M, ed. International Colloquium on Structural Information and Communication Complexity. Vol 13298. LNCS. Springer Nature; 2022:1-20. doi:10.1007/978-3-031-09993-9_1
Balliu, A., Hirvonen, J., Melnyk, D., Olivetti, D., Rybicki, J., & Suomela, J. (2022). Local mending. In M. Parter (Ed.), International Colloquium on Structural Information and Communication Complexity (Vol. 13298, pp. 1–20). Paderborn, Germany: Springer Nature. https://doi.org/10.1007/978-3-031-09993-9_1
Balliu, Alkida, Juho Hirvonen, Darya Melnyk, Dennis Olivetti, Joel Rybicki, and Jukka Suomela. “Local Mending.” In International Colloquium on Structural Information and Communication Complexity, edited by Merav Parter, 13298:1–20. LNCS. Springer Nature, 2022. https://doi.org/10.1007/978-3-031-09993-9_1.
A. Balliu, J. Hirvonen, D. Melnyk, D. Olivetti, J. Rybicki, and J. Suomela, “Local mending,” in International Colloquium on Structural Information and Communication Complexity, Paderborn, Germany, 2022, vol. 13298, pp. 1–20.
Balliu A, Hirvonen J, Melnyk D, Olivetti D, Rybicki J, Suomela J. 2022. Local mending. International Colloquium on Structural Information and Communication Complexity. SIROCCO: Structural Information and Communication ComplexityLNCS vol. 13298, 1–20.
Balliu, Alkida, et al. “Local Mending.” International Colloquium on Structural Information and Communication Complexity, edited by Merav Parter, vol. 13298, Springer Nature, 2022, pp. 1–20, doi:10.1007/978-3-031-09993-9_1.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data ISTA Research Explorer

Sources

arXiv 2102.08703

Search this title in

Google Scholar
ISBN Search