Alkida Balliu · Juho Hirvonen · Darya Melnyk · Dennis Olivetti · Joel Rybicki · Jukka Suomela

Local mending

SIROCCO 2022 · 29th International Colloquium on Structural Information and Communication Complexity, Paderborn, Germany, June–July 2022 · doi:10.1007/978-3-031-09993-9_1

authors’ version publisher’s version arXiv.org

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 $\Pi$ can be solved in $O(\log^* n)$, there is always a restriction $\Pi' \subseteq \Pi$ 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)$, $\Theta(\log n)$, or $\Theta(n)$, while in general graphs the structure is much more diverse.

Publication

Merav Parter (Ed.): Structural Information and Communication Complexity, 29th International Colloquium, SIROCCO 2022, Paderborn, Germany, June 27–29, 2022, Proceedings, volume 13298 of Lecture Notes in Computer Science, pages 1–20, Springer, Berlin, 2022

ISBN 978-3-031-09993-9

Links

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.