Mending Partial Solutions with Few Changes

Thumbnail Image
Access rights
openAccess
Journal Title
Journal ISSN
Volume Title
Conference article in proceedings
This publication is imported from Aalto University research portal.
View publication in the Research portal
View/Open full text file from the Research portal
Other link related to publication
Author
Date
2023-02-01
Department
Department of Computer Science
Computer Science Professors
Major/Subject
Mcode
Degree programme
Language
en
Pages
Series
26th International Conference on Principles of Distributed Systems, OPODIS 2022, Leibniz International Proceedings in Informatics, LIPIcs, Volume 253
Abstract
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 Θ(logk 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.
Description
Funding Information: This work was supported in part by the Academy of Finland, Grant 333837. Publisher Copyright: © Darya Melnyk, Jukka Suomela, and Neven Villani.
Keywords
LCL problems, mending, volume model
Other note
DOI
10.4230/LIPIcs.OPODIS.2022.21
Citation
Melnyk , D , Suomela , J & Villani , N 2023 , Mending Partial Solutions with Few Changes . in E Hillel , R Palmieri & E Riviere (eds) , 26th International Conference on Principles of Distributed Systems, OPODIS 2022 . , 21 , Leibniz International Proceedings in Informatics, LIPIcs , vol. 253 , Schloss Dagstuhl - Leibniz-Zentrum für Informatik , International Conference on Principles of Distributed Systems , Brussels , Belgium , 13/12/2022 . https://doi.org/10.4230/LIPIcs.OPODIS.2022.21
Permanent link to this item
https://urn.fi/URN:NBN:fi:aalto-202308234988
Collections
[article-cris] Perustieteiden korkeakoulu / SCI