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

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.

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