---
_id: '11707'
abstract:
- lang: eng
  text: 'In this work we introduce the graph-theoretic notion of mendability: for
    each locally checkable graph problem we can define its mending radius, which captures
    the idea of how far one needs to modify a partial solution in order to “patch
    a hole.” We explore how mendability is connected to the existence of efficient
    algorithms, especially in distributed, parallel, and fault-tolerant settings.
    It is easy to see that O(1)-mendable problems are also solvable in O(log∗n) rounds
    in the LOCAL model of distributed computing. One of the surprises is that in paths
    and cycles, a converse also holds in the following sense: if a problem Π can be
    solved in O(log∗n), there is always a restriction Π′⊆Π that is still efficiently
    solvable but that is also O(1)-mendable. We also explore the structure of the
    landscape of mendability. For example, we show that in trees, the mending radius
    of any locally checkable problem is O(1), Θ(logn), or Θ(n), while in general graphs
    the structure is much more diverse.'
acknowledgement: This project has received funding from the European Union’s Horizon
  2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement
  No 840605. This work was supported in part by the Academy of Finland, Grants 314888
  and 333837. The authors would also like to thank David Harris, Neven Villani, and
  the anonymous reviewers for their very helpful comments and feedback on previous
  versions of this work.
article_processing_charge: No
arxiv: 1
author:
- first_name: Alkida
  full_name: Balliu, Alkida
  last_name: Balliu
- first_name: Juho
  full_name: Hirvonen, Juho
  last_name: Hirvonen
- first_name: Darya
  full_name: Melnyk, Darya
  last_name: Melnyk
- first_name: Dennis
  full_name: Olivetti, Dennis
  last_name: Olivetti
- first_name: Joel
  full_name: Rybicki, Joel
  id: 334EFD2E-F248-11E8-B48F-1D18A9856A87
  last_name: Rybicki
  orcid: 0000-0002-6432-6646
- first_name: Jukka
  full_name: Suomela, Jukka
  last_name: Suomela
citation:
  ama: 'Balliu A, Hirvonen J, Melnyk D, Olivetti D, Rybicki J, Suomela J. Local mending.
    In: Parter M, ed. <i>International Colloquium on Structural Information and Communication
    Complexity</i>. Vol 13298. LNCS. Springer Nature; 2022:1-20. doi:<a href="https://doi.org/10.1007/978-3-031-09993-9_1">10.1007/978-3-031-09993-9_1</a>'
  apa: 'Balliu, A., Hirvonen, J., Melnyk, D., Olivetti, D., Rybicki, J., &#38; Suomela,
    J. (2022). Local mending. In M. Parter (Ed.), <i>International Colloquium on Structural
    Information and Communication Complexity</i> (Vol. 13298, pp. 1–20). Paderborn,
    Germany: Springer Nature. <a href="https://doi.org/10.1007/978-3-031-09993-9_1">https://doi.org/10.1007/978-3-031-09993-9_1</a>'
  chicago: Balliu, Alkida, Juho Hirvonen, Darya Melnyk, Dennis Olivetti, Joel Rybicki,
    and Jukka Suomela. “Local Mending.” In <i>International Colloquium on Structural
    Information and Communication Complexity</i>, edited by Merav Parter, 13298:1–20.
    LNCS. Springer Nature, 2022. <a href="https://doi.org/10.1007/978-3-031-09993-9_1">https://doi.org/10.1007/978-3-031-09993-9_1</a>.
  ieee: A. Balliu, J. Hirvonen, D. Melnyk, D. Olivetti, J. Rybicki, and J. Suomela,
    “Local mending,” in <i>International Colloquium on Structural Information and
    Communication Complexity</i>, Paderborn, Germany, 2022, vol. 13298, pp. 1–20.
  ista: 'Balliu A, Hirvonen J, Melnyk D, Olivetti D, Rybicki J, Suomela J. 2022. Local
    mending. International Colloquium on Structural Information and Communication
    Complexity. SIROCCO: Structural Information and Communication ComplexityLNCS vol.
    13298, 1–20.'
  mla: Balliu, Alkida, et al. “Local Mending.” <i>International Colloquium on Structural
    Information and Communication Complexity</i>, edited by Merav Parter, vol. 13298,
    Springer Nature, 2022, pp. 1–20, doi:<a href="https://doi.org/10.1007/978-3-031-09993-9_1">10.1007/978-3-031-09993-9_1</a>.
  short: A. Balliu, J. Hirvonen, D. Melnyk, D. Olivetti, J. Rybicki, J. Suomela, in:,
    M. Parter (Ed.), International Colloquium on Structural Information and Communication
    Complexity, Springer Nature, 2022, pp. 1–20.
conference:
  end_date: 2022-06-29
  location: Paderborn, Germany
  name: 'SIROCCO: Structural Information and Communication Complexity'
  start_date: 2022-06-27
date_created: 2022-07-31T22:01:49Z
date_published: 2022-06-25T00:00:00Z
date_updated: 2023-08-03T12:16:29Z
day: '25'
department:
- _id: DaAl
doi: 10.1007/978-3-031-09993-9_1
ec_funded: 1
editor:
- first_name: Merav
  full_name: Parter, Merav
  last_name: Parter
external_id:
  arxiv:
  - '2102.08703'
  isi:
  - '000876977400001'
intvolume: '     13298'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/2102.08703
month: '06'
oa: 1
oa_version: Preprint
page: 1-20
project:
- _id: 26A5D39A-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '840605'
  name: Coordination in constrained and natural distributed systems
publication: International Colloquium on Structural Information and Communication
  Complexity
publication_identifier:
  eissn:
  - 1611-3349
  isbn:
  - '9783031099922'
  issn:
  - 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
series_title: LNCS
status: public
title: Local mending
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 13298
year: '2022'
...