Local Mending

Alkida Balliu; Juho Hirvonen; Darya Melnyk; Dennis Olivetti; Joel Rybicki; Jukka Suomela

doi:10.1007/978-3-031-09993-9_1

Local Mending

Alkida Balliu, Juho Hirvonen, Darya Melnyk^*, Dennis Olivetti, Joel Rybicki, Jukka Suomela

^*Corresponding author for this work

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

3 Citations (Scopus)

Abstract

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), Θ(log n), or Θ(n), while in general graphs the structure is much more diverse.

Original language	English
Title of host publication	Structural Information and Communication Complexity - 29th International Colloquium, SIROCCO 2022, Proceedings
Editors	Merav Parter
Publisher	Springer
Pages	1-20
Number of pages	20
ISBN (Print)	978-3-031-09992-2
DOIs	https://doi.org/10.1007/978-3-031-09993-9_1
Publication status	Published - 2022
MoE publication type	A4 Conference publication
Event	International Colloquium on Structural Information and Communication Complexity - Paderborn, Germany Duration: 27 Jun 2022 → 29 Jun 2022 Conference number: 29

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Publisher	Springer
Volume	13298 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	International Colloquium on Structural Information and Communication Complexity
Abbreviated title	SIROCCO
Country/Territory	Germany
City	Paderborn
Period	27/06/2022 → 29/06/2022

Keywords

Distributed algorithms
Dynamic algorithms
Fault tolerance
LCL problems
Mendability
Parallel algorithms

Access to Document

10.1007/978-3-031-09993-9_1

https://arxiv.org/abs/2102.08703

Cite this

Balliu, A., Hirvonen, J., Melnyk, D., Olivetti, D., Rybicki, J., & Suomela, J. (2022). Local Mending. In M. Parter (Ed.), Structural Information and Communication Complexity - 29th International Colloquium, SIROCCO 2022, Proceedings (pp. 1-20). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13298 LNCS). Springer. https://doi.org/10.1007/978-3-031-09993-9_1

@inproceedings{11994d7a774b471e90c53ed8a56a3ca2,

title = "Local Mending",

abstract = "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), Θ(log n), or Θ(n), while in general graphs the structure is much more diverse.",

keywords = "Distributed algorithms, Dynamic algorithms, Fault tolerance, LCL problems, Mendability, Parallel algorithms",

author = "Alkida Balliu and Juho Hirvonen and Darya Melnyk and Dennis Olivetti and Joel Rybicki and Jukka Suomela",

note = "| openaire: EC/H2020/840605/EU//CoCoNat Funding Information: Acknowledgements. This project has received funding from the European Union{\textquoteright}s Horizon 2020 research and innovation programme under the Marie Sk lodowska-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. Publisher Copyright: {\textcopyright} 2022, Springer Nature Switzerland AG.; International Colloquium on Structural Information and Communication Complexity, SIROCCO ; Conference date: 27-06-2022 Through 29-06-2022",

year = "2022",

doi = "10.1007/978-3-031-09993-9_1",

language = "English",

isbn = "978-3-031-09992-2",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "1--20",

editor = "Merav Parter",

booktitle = "Structural Information and Communication Complexity - 29th International Colloquium, SIROCCO 2022, Proceedings",

address = "Germany",

}

Balliu, A, Hirvonen, J, Melnyk, D, Olivetti, D, Rybicki, J & Suomela, J 2022, Local Mending. in M Parter (ed.), Structural Information and Communication Complexity - 29th International Colloquium, SIROCCO 2022, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13298 LNCS, Springer, pp. 1-20, International Colloquium on Structural Information and Communication Complexity, Paderborn, Germany, 27/06/2022. https://doi.org/10.1007/978-3-031-09993-9_1

Local Mending. / Balliu, Alkida; Hirvonen, Juho; Melnyk, Darya et al.
Structural Information and Communication Complexity - 29th International Colloquium, SIROCCO 2022, Proceedings. ed. / Merav Parter. Springer, 2022. p. 1-20 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13298 LNCS).

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

TY - GEN

T1 - Local Mending

AU - Balliu, Alkida

AU - Hirvonen, Juho

AU - Melnyk, Darya

AU - Olivetti, Dennis

AU - Rybicki, Joel

AU - Suomela, Jukka

N1 - Conference code: 29

PY - 2022

Y1 - 2022

N2 - 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), Θ(log n), or Θ(n), while in general graphs the structure is much more diverse.

AB - 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), Θ(log n), or Θ(n), while in general graphs the structure is much more diverse.

KW - Distributed algorithms

KW - Dynamic algorithms

KW - Fault tolerance

KW - LCL problems

KW - Mendability

KW - Parallel algorithms

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

U2 - 10.1007/978-3-031-09993-9_1

DO - 10.1007/978-3-031-09993-9_1

M3 - Conference article in proceedings

AN - SCOPUS:85134351744

SN - 978-3-031-09992-2

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 1

EP - 20

BT - Structural Information and Communication Complexity - 29th International Colloquium, SIROCCO 2022, Proceedings

A2 - Parter, Merav

PB - Springer

T2 - International Colloquium on Structural Information and Communication Complexity

Y2 - 27 June 2022 through 29 June 2022

ER -

Balliu A, Hirvonen J, Melnyk D, Olivetti D, Rybicki J, Suomela J. Local Mending. In Parter M, editor, Structural Information and Communication Complexity - 29th International Colloquium, SIROCCO 2022, Proceedings. Springer. 2022. p. 1-20. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-09993-9_1

Local Mending

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

LocalMend /Suomela: Local Checking, Solving, and MendingNew Perspectives of Distributed Computing (LocalMend)

Towards a complexity theory of distributed network computing

Cite this

Local Mending

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)

Towards a complexity theory of distributed network computing

Cite this

LocalMend /Suomela: Local Checking, Solving, and MendingNew Perspectives of Distributed Computing (LocalMend)