Projects per year
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 Θ(log^{k} n). Hence the mendability of LCL problems on trees is a much more finegrained question than what one would expect based on the mending radius alone.
Original language  English 

Title of host publication  26th International Conference on Principles of Distributed Systems, OPODIS 2022 
Editors  Eshcar Hillel, Roberto Palmieri, Etienne Riviere 
Publisher  Schloss Dagstuhl  LeibnizZentrum für Informatik 
ISBN (Electronic)  9783959772655 
DOIs  
Publication status  Published  1 Feb 2023 
MoE publication type  A4 Conference publication 
Event  International Conference on Principles of Distributed Systems  Brussels, Belgium Duration: 13 Dec 2022 → 15 Dec 2022 Conference number: 26 
Publication series
Name  Leibniz International Proceedings in Informatics, LIPIcs 

Volume  253 
ISSN (Print)  18688969 
Conference
Conference  International Conference on Principles of Distributed Systems 

Abbreviated title  OPODIS 
Country/Territory  Belgium 
City  Brussels 
Period  13/12/2022 → 15/12/2022 
Keywords
 LCL problems
 mending
 volume model
Fingerprint
Dive into the research topics of 'Mending Partial Solutions with Few Changes'. Together they form a unique fingerprint.Projects
 1 Finished

LocalMend /Suomela: Local Checking, Solving, and Mending—New Perspectives of Distributed Computing (LocalMend)
Suomela, J. (Principal investigator), Lievonen, H. (Project Member), Melnyk, D. (Project Member), Vahidi, H. (Project Member), Studeny, J. (Project Member) & Akbari, A. (Project Member)
01/09/2020 → 31/08/2024
Project: Academy of Finland: Other research funding