LIPIcs.DISC.2021.49.pdf
- Filesize: 0.5 MB
- 4 pages
Document
Brief Announcement: Local Certification of Graph Decompositions and Applications to Minor-Free Classes
Authors
Nicolas Bousquet 
,
Laurent Feuilloley ,
Théo Pierron
-
Part of:
Volume:
35th International Symposium on Distributed Computing (DISC 2021)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Distributed Computing (DISC) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2021-10-04
File
Document Identifiers
Author Details
Cite As Get BibTex
Nicolas Bousquet, Laurent Feuilloley, and Théo Pierron. Brief Announcement: Local Certification of Graph Decompositions and Applications to Minor-Free Classes. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 49:1-49:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.DISC.2021.49
Abstract
Local certification consists in assigning labels to the nodes of a network to certify that some given property is satisfied, in such a way that the labels can be checked locally. In the last few years, certification of graph classes received a considerable attention. The goal is to certify that a graph G belongs to a given graph class 𝒢. Such certifications with labels of size O(log n) (where n is the size of the network) exist for trees, planar graphs and graphs embedded on surfaces. Feuilloley et al. ask if this can be extended to any class of graphs defined by a finite set of forbidden minors. In this paper, we develop new decomposition tools for graph certification, and apply them to show that for every small enough minor H, H-minor-free graphs can indeed be certified with labels of size O(log n). We also show matching lower bounds with a new simple proof technique.
Subject Classification
ACM Subject Classification
- Theory of computation → Distributed algorithms
Keywords
- Local certification
- proof-labeling schemes
- locally checkable proofs
- graph decompositions
- minor-free graphs
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Kenneth Appel, Wolfgang Haken, et al. Every planar map is four colorable. Bulletin of the American mathematical Society, 82(5):711-712, 1976.
- Nicolas Bousquet, Laurent Feuilloley, and Théo Pierron. Local certification of graph decompositions and applications to minor-free classes. CoRR, abs/2108.00059, 2021. URL: http://arxiv.org/abs/2108.00059.
- Keren Censor-Hillel, Ami Paz, and Mor Perry. Approximate proof-labeling schemes. Theor. Comput. Sci., 811:112-124, 2020. URL: https://doi.org/10.1016/j.tcs.2018.08.020.
-
Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas. The strong perfect graph theorem. Annals of mathematics, pages 51-229, 2006.
- Louis Esperet and Benjamin Lévêque. Local certification of graphs on surfaces. CoRR, abs/2102.04133, 2021. URL: http://arxiv.org/abs/2102.04133.
-
Laurent Feuilloley. Introduction to local certification. CoRR, abs/1910.12747, 2019.
- Laurent Feuilloley, Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, Éric Rémila, and Ioan Todinca. Compact distributed certification of planar graphs. In PODC '20: ACM Symposium on Principles of Distributed Computing, pages 319-328. ACM, 2020. URL: https://doi.org/10.1145/3382734.3404505.
-
Laurent Feuilloley, Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, Eric Rémila, and Ioan Todinca. Local certification of graphs with bounded genus. CoRR, abs/2007.08084, 2020.
- Mika Göös and Jukka Suomela. Locally checkable proofs in distributed computing. Theory of Computing, 12(19):1-33, 2016. URL: https://doi.org/10.4086/toc.2016.v012a019.
- Amos Korman, Shay Kutten, and David Peleg. Proof labeling schemes. Distributed Computing, 22(4):215-233, 2010. URL: https://doi.org/10.1007/s00446-010-0095-3.