OPODIS 2022 · 25th International Conference on Principles of Distributed Systems, Brussels, Belgium, December 2022

In this paper, we study the notion of mending, i.e. given a partial solution to a graph problem, we investigate how much effort is needed to turn it into a proper solution. For example, if we have a partial coloring of a graph, how hard is it to turn it into a proper coloring?

In prior work (SIROCCO 2022), this question was formalized and studied from the perspective of *mending radius*: if there is a hole that we need to patch, how *far* do we need to modify the solution? In this work, we investigate a complementary notion of *mending volume*: how *many* nodes need to be modified to patch a hole?

We focus on the case of locally checkable labeling problems (LCLs) in trees, and show that already in this setting there are two infinite hierarchies of problems: for infinitely many values $0 < \alpha \le 1$, there is an LCL problem with mending volume $\Theta(n^\alpha)$, and for infinitely many values $k \ge 1$, there is an LCL problem with mending volume $\Theta(\log^k n)$. Hence the mendability of LCL problems on trees is a much more fine-grained question than what one would expect based on the mending radius alone.

We define three variants of the theme: (1) *existential* mending volume, i.e., how many nodes need to be modified, (2) *expected* mending volume, i.e., how many nodes we need to explore to find a patch if we use randomness, and (3) *deterministic* mending volume, i.e., how many nodes we need to explore if we use a deterministic algorithm. We show that all three notions are distinct from each other, and we analyze the landscape of the complexities of LCL problems for the respective models.