Mending Partial Solutions with Few Changes

Simple item page
dc.contributorAalto-yliopistofi
dc.contributorAalto Universityen
dc.contributor.authorMelnyk, Daryaen_US
dc.contributor.authorSuomela, Jukkaen_US
dc.contributor.authorVillani, Nevenen_US
dc.contributor.departmentDepartment of Computer Scienceen
dc.contributor.editorHillel, Eshcaren_US
dc.contributor.editorPalmieri, Robertoen_US
dc.contributor.editorRiviere, Etienneen_US
dc.contributor.groupauthorProfessorship Suomela J.en
dc.contributor.groupauthorComputer Science Professorsen
dc.contributor.groupauthorComputer Science - Algorithms and Theoretical Computer Science (TCS)en
dc.contributor.groupauthorComputer Science - Large-scale Computing and Data Analysis (LSCA)en
dc.date.accessioned2023-08-23T06:07:51Z
dc.date.available2023-08-23T06:07:51Z
dc.date.issued2023-02-01en_US
dc.descriptionFunding Information: This work was supported in part by the Academy of Finland, Grant 333837. Publisher Copyright: © Darya Melnyk, Jukka Suomela, and Neven Villani.
dc.description.abstractIn 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.en
dc.description.versionPeer revieweden
dc.format.mimetypeapplication/pdfen_US
dc.identifier.citationMelnyk, 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.21en
dc.identifier.doi10.4230/LIPIcs.OPODIS.2022.21en_US
dc.identifier.isbn9783959772655
dc.identifier.issn1868-8969
dc.identifier.otherPURE UUID: 626f479a-760f-49ba-895e-020d2c09d902en_US
dc.identifier.otherPURE ITEMURL: https://research.aalto.fi/en/publications/626f479a-760f-49ba-895e-020d2c09d902en_US
dc.identifier.otherPURE LINK: http://www.scopus.com/inward/record.url?scp=85148613458&partnerID=8YFLogxKen_US
dc.identifier.otherPURE FILEURL: https://research.aalto.fi/files/119072608/SCI_Melnyk_etal_OPODIS_2022.pdfen_US
dc.identifier.urihttps://aaltodoc.aalto.fi/handle/123456789/122642
dc.identifier.urnURN:NBN:fi:aalto-202308234988
dc.language.isoenen
dc.relation.ispartofInternational Conference on Principles of Distributed Systemsen
dc.relation.ispartofseries26th International Conference on Principles of Distributed Systems, OPODIS 2022en
dc.relation.ispartofseriesLeibniz International Proceedings in Informatics, LIPIcsen
dc.relation.ispartofseriesVolume 253en
dc.rightsopenAccessen
dc.subject.keywordLCL problemsen_US
dc.subject.keywordmendingen_US
dc.subject.keywordvolume modelen_US
dc.titleMending Partial Solutions with Few Changesen
dc.typeA4 Artikkeli konferenssijulkaisussafi
dc.type.versionpublishedVersion
Files
Collections
[article-cris] Perustieteiden korkeakoulu / SCI