Local certification of forbidden subgraphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913529753239552 |
|---|---|
| author | Bousquet, Nicolas Cook, Linda Feuilloley, Laurent Pierron, Théo Zeitoun, Sébastien |
| author_facet | Bousquet, Nicolas Cook, Linda Feuilloley, Laurent Pierron, Théo Zeitoun, Sébastien |
| contents | Detecting specific structures in a network has been a very active theme of research in distributed computing for at least a decade. In this paper, we start the study of subgraph detection from the perspective of local certification. Remember that a local certification is a distributed mechanism enabling the nodes of a network to check the correctness of the current configuration, thanks to small pieces of information called certificates. Our main question is: For a given graph $H$, what is the minimum certificate size that allows checking that the network does not contain $H$ as a (possibly induced) subgraph?
We show a variety of lower and upper bounds, uncovering an interesting interplay between the optimal certificate size, the size of the forbidden subgraph, and the locality of the verification. Along the way we introduce several new technical tools, in particular what we call the \emph{layered map}, which is not specific to forbidden subgraphs and that we expect to be useful for certifying many other properties. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_12148 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Local certification of forbidden subgraphs Bousquet, Nicolas Cook, Linda Feuilloley, Laurent Pierron, Théo Zeitoun, Sébastien Distributed, Parallel, and Cluster Computing Discrete Mathematics Data Structures and Algorithms Detecting specific structures in a network has been a very active theme of research in distributed computing for at least a decade. In this paper, we start the study of subgraph detection from the perspective of local certification. Remember that a local certification is a distributed mechanism enabling the nodes of a network to check the correctness of the current configuration, thanks to small pieces of information called certificates. Our main question is: For a given graph $H$, what is the minimum certificate size that allows checking that the network does not contain $H$ as a (possibly induced) subgraph? We show a variety of lower and upper bounds, uncovering an interesting interplay between the optimal certificate size, the size of the forbidden subgraph, and the locality of the verification. Along the way we introduce several new technical tools, in particular what we call the \emph{layered map}, which is not specific to forbidden subgraphs and that we expect to be useful for certifying many other properties. |
| title | Local certification of forbidden subgraphs |
| topic | Distributed, Parallel, and Cluster Computing Discrete Mathematics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2402.12148 |