Mending Partial Solutions with Few Changes
Loading...
Access rights
openAccess
publishedVersion
URL
Journal Title
Journal ISSN
Volume Title
A4 Artikkeli konferenssijulkaisussa
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Date
Department
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
Other note
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