2026-08-12T08:04:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17641 2024-03-06T11:00:11Z ddc:004 open_access

Mending Partial Solutions with Few Changes Melnyk, Darya Suomela, Jukka Villani, Neven mending LCL problems volume model In this paper, we study the notion of mending: given a partial solution to a graph problem, how much effort is needed to take one step towards a proper solution? For example, if we have a partial coloring of a graph, how hard is it to properly color one more node? 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 < α ≤ 1, there is an LCL problem with mending volume Θ(n^α), and for infinitely many values k ≥ 1, there is an LCL problem with mending volume Θ(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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Darya Melnyk and Jukka Suomela and Neven Villani 2023 Is Part Of LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.OPODIS.2022.21 urn:nbn:de:0030-drops-176413 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.21 eng https://creativecommons.org/licenses/by/4.0/legalcode