Mending Partial Solutions with Few Changes

Darya Melnyk; Jukka Suomela; Neven Villani

doi:10.4230/LIPIcs.OPODIS.2022.21

Mending Partial Solutions with Few Changes

Darya Melnyk^*, Jukka Suomela^*, Neven Villani^*

^*Corresponding author for this work

École normale supérieure Paris-Saclay

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceedings › Scientific › peer-review

49 Downloads (Pure)

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 fine-grained 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 - Leibniz-Zentrum für Informatik
ISBN (Electronic)	978-3-95977-265-5
DOIs	https://doi.org/10.4230/LIPIcs.OPODIS.2022.21
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)	1868-8969

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

Access to Document

10.4230/LIPIcs.OPODIS.2022.21Licence: CC BY

SCI_Melnyk_etal_OPODIS_2022Final published version, 486 KBLicence: CC BY

Cite this

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 Article 21 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 253). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.OPODIS.2022.21

@inproceedings{626f479a760f49ba895e020d2c09d902,

title = "Mending Partial Solutions with Few Changes",

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.",

keywords = "LCL problems, mending, volume model",

author = "Darya Melnyk and Jukka Suomela and Neven Villani",

note = "Funding Information: This work was supported in part by the Academy of Finland, Grant 333837. Publisher Copyright: {\textcopyright} Darya Melnyk, Jukka Suomela, and Neven Villani.; International Conference on Principles of Distributed Systems, OPODIS ; Conference date: 13-12-2022 Through 15-12-2022",

year = "2023",

month = feb,

day = "1",

doi = "10.4230/LIPIcs.OPODIS.2022.21",

language = "English",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",

editor = "Eshcar Hillel and Roberto Palmieri and Etienne Riviere",

booktitle = "26th International Conference on Principles of Distributed Systems, OPODIS 2022",

address = "Germany",

}

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

Mending Partial Solutions with Few Changes. / Melnyk, Darya; Suomela, Jukka; Villani, Neven.
26th International Conference on Principles of Distributed Systems, OPODIS 2022. ed. / Eshcar Hillel; Roberto Palmieri; Etienne Riviere. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. 21 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 253).

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceedings › Scientific › peer-review

TY - GEN

T1 - Mending Partial Solutions with Few Changes

AU - Melnyk, Darya

AU - Suomela, Jukka

AU - Villani, Neven

N1 - Conference code: 26

PY - 2023/2/1

Y1 - 2023/2/1

N2 - 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.

AB - 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.

KW - LCL problems

KW - mending

KW - volume model

UR - http://www.scopus.com/inward/record.url?scp=85148613458&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.OPODIS.2022.21

DO - 10.4230/LIPIcs.OPODIS.2022.21

M3 - Conference article in proceedings

AN - SCOPUS:85148613458

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 26th International Conference on Principles of Distributed Systems, OPODIS 2022

A2 - Hillel, Eshcar

A2 - Palmieri, Roberto

A2 - Riviere, Etienne

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

T2 - International Conference on Principles of Distributed Systems

Y2 - 13 December 2022 through 15 December 2022

ER -

Mending Partial Solutions with Few Changes

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

LocalMend /Suomela: Local Checking, Solving, and Mending—New Perspectives of Distributed Computing (LocalMend)

Cite this

Mending Partial Solutions with Few Changes

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Projects

LocalMend /Suomela: Local Checking, Solving, and Mending—New Perspectives of Distributed Computing (LocalMend)

Cite this