Darya Melnyk · Jukka Suomela · Neven Villani

Mending partial solutions with few changes

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

authors’ version arXiv.org

Abstract

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.

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.