DROPS

Document

DOI: 10.4230/LIPIcs.OPODIS.2022.21

Mending Partial Solutions with Few Changes

Authors: Darya Melnyk, Jukka Suomela, and Neven Villani

Published in: LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022)

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.

Cite as

Darya Melnyk, Jukka Suomela, and Neven Villani. Mending Partial Solutions with Few Changes. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 21:1-21:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{melnyk_et_al:LIPIcs.OPODIS.2022.21,
  author =	{Melnyk, Darya and Suomela, Jukka and Villani, Neven},
  title =	{{Mending Partial Solutions with Few Changes}},
  booktitle =	{26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
  pages =	{21:1--21:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-265-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{253},
  editor =	{Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.21},
  URN =		{urn:nbn:de:0030-drops-176413},
  doi =		{10.4230/LIPIcs.OPODIS.2022.21},
  annote =	{Keywords: mending, LCL problems, volume model}
}

Search Results

Documents authored by Villani, Neven

Mending Partial Solutions with Few Changes

Abstract

Cite as

Thanks for your feedback!

Could not send message