Document Open Access Logo

Local Certification of Graph Decompositions and Applications to Minor-Free Classes

Authors Nicolas Bousquet , Laurent Feuilloley , Théo Pierron

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2021.22.pdf
  • Filesize: 0.68 MB
  • 17 pages

Document Identifiers

Author Details

Nicolas Bousquet
  • Univ. Lyon, Université Lyon 1, LIRIS UMR CNRS 5205, F-69621, Lyon, France
Laurent Feuilloley
  • Univ. Lyon, Université Lyon 1, LIRIS UMR CNRS 5205, F-69621, Lyon, France
Théo Pierron
  • Univ. Lyon, Université Lyon 1, LIRIS UMR CNRS 5205, F-69621, Lyon, France

Funding

This work was supported by ANR project GrR (ANR-18-CE40-0032).

Acknowledgements

The authors thank the reviewers for the their comments, and Jens M. Schmidt for pointing out a mistake a previous version.

Cite AsGet BibTex

Nicolas Bousquet, Laurent Feuilloley, and Théo Pierron. Local Certification of Graph Decompositions and Applications to Minor-Free Classes. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 22:1-22:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.OPODIS.2021.22

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 work, 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 using a new 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)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Yehuda Afek, Shay Kutten, and Moti Yung. Memory-efficient self stabilizing protocols for general networks. In WDAG '90, volume 486, pages 15-28, 1990. URL: https://doi.org/10.1007/3-540-54099-7_2.
  2. Kenneth Appel, Wolfgang Haken, et al. Every planar map is four colorable. Bulletin of the American mathematical Society, 82(5):711-712, 1976. Google Scholar
  3. Giuseppe Di Battista and Roberto Tamassia. Incremental planarity testing (extended abstract). In FOCS 89, pages 436-441, 1989. URL: https://doi.org/10.1109/SFCS.1989.63515.
  4. 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.
  5. Zvika Brakerski and Boaz Patt-Shamir. Distributed discovery of large near-cliques. Distributed Comput., 24(2):79-89, 2011. URL: https://doi.org/10.1007/s00446-011-0132-x.
  6. Keren Censor-Hillel, Eldar Fischer, Gregory Schwartzman, and Yadu Vasudev. Fast distributed algorithms for testing graph properties. Distributed Comput., 32(1):41-57, 2019. URL: https://doi.org/10.1007/s00446-018-0324-8.
  7. Keren Censor-Hillel, Orr Fischer, Tzlil Gonen, François Le Gall, Dean Leitersdorf, and Rotem Oshman. Fast distributed algorithms for girth, cycles and small subgraphs. In DISC 2020, volume 179 of LIPIcs, pages 33:1-33:17, 2020. URL: https://doi.org/10.4230/LIPIcs.DISC.2020.33.
  8. 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.
  9. Joseph Cheriyan and S. N. Maheshwari. Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs. J. Algorithms, 9(4):507-537, 1988. URL: https://doi.org/10.1016/0196-6774(88)90015-6.
  10. Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas. The strong perfect graph theorem. Annals of mathematics, pages 51-229, 2006. Google Scholar
  11. Shlomi Dolev. Self-Stabilization. MIT Press, 2000. URL: http://www.cs.bgu.ac.il/%7Edolev/book/book.html.
  12. David Eppstein. Parallel recognition of series-parallel graphs. Inf. Comput., 98(1):41-55, 1992. URL: https://doi.org/10.1016/0890-5401(92)90041-D.
  13. Louis Esperet and Benjamin Lévêque. Local certification of graphs on surfaces. CoRR, abs/2102.04133, 2021. Google Scholar
  14. Laurent Feuilloley. Introduction to local certification. CoRR, abs/1910.12747, 2019. Google Scholar
  15. Laurent Feuilloley. Bibliography of distributed approximation on structurally sparse graph classes. CoRR, abs/2001.08510, 2020. Google Scholar
  16. Laurent Feuilloley and Pierre Fraigniaud. Survey of distributed decision. Bulletin of the EATCS, 119, 2016. URL: http://bulletin.eatcs.org/index.php/beatcs/article/view/411/391, URL: http://arxiv.org/abs/1606.04434.
  17. Laurent Feuilloley, Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, Éric Rémila, and Ioan Todinca. Compact distributed certification of planar graphs. In PODC '20, pages 319-328. ACM, 2020. URL: https://doi.org/10.1145/3382734.3404505.
  18. 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. Google Scholar
  19. Laurent Feuilloley and Juho Hirvonen. Local verification of global proofs. In DISC 2018, volume 121 of LIPIcs, pages 25:1-25:17, 2018. URL: https://doi.org/10.4230/LIPIcs.DISC.2018.25.
  20. Pierre Fraigniaud and Dennis Olivetti. Distributed detection of cycles. ACM Trans. Parallel Comput., 6(3):12:1-12:20, 2019. URL: https://doi.org/10.1145/3322811.
  21. Mohsen Ghaffari and Bernhard Haeupler. Distributed algorithms for planar networks II: low-congestion shortcuts, mst, and min-cut. In SODA 2016, pages 202-219. SIAM, 2016. URL: https://doi.org/10.1137/1.9781611974331.ch16.
  22. Mohsen Ghaffari and Bernhard Haeupler. Low-congestion shortcuts for graphs excluding dense minors. In PODC 2021, page To appear., 2021. Google Scholar
  23. 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.
  24. Bernhard Haeupler, Taisuke Izumi, and Goran Zuzic. Near-optimal low-congestion shortcuts on bounded parameter graphs. In DISC 2016, volume 9888, pages 158-172. Springer, 2016. URL: https://doi.org/10.1007/978-3-662-53426-7_12.
  25. Bernhard Haeupler, Jason Li, and Goran Zuzic. Minor excluded network families admit fast distributed algorithms. In PODC 2018, pages 465-474, 2018. Google Scholar
  26. 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.
  27. Alexandr V Kostochka. The minimum hadwiger number for graphs with a given mean degree of vertices. Metody Diskret. Analiz., 38:37-58, 1982. Google Scholar
  28. Lee F. Mondshein. Combinatorial Ordering and the Geometric Embedding of Graphs. PhD thesis, M.I.T. Lincoln Laboratory / Harvard University, 1971. Google Scholar
  29. Pedro Montealegre, Diego Ramírez-Romero, and Iván Rapaport. Compact distributed interactive proofs for the recognition of cographs and distance-hereditary graphs. CoRR, abs/2012.03185, 2020. Google Scholar
  30. Moni Naor, Merav Parter, and Eylon Yogev. The power of distributed verifiers in interactive proofs. In SODA 2020, pages 1096-115. SIAM, 2020. URL: https://doi.org/10.1137/1.9781611975994.67.
  31. Neil Robertson and Paul D Seymour. Graph minors—a survey. Surveys in combinatorics, 103:153-171, 1985. Google Scholar
  32. Jens M. Schmidt. Mondshein sequences (a.k.a. (2, 1)-orders). SIAM J. Comput., 45(6):1985-2003, 2016. URL: https://doi.org/10.1137/15M1030030.
  33. Andrew Thomason. An extremal function for contractions of graphs. In Mathematical Proceedings of the Cambridge Philosophical Society, volume 95(2), pages 261-265. Cambridge University Press, 1984. Google Scholar
  34. K. Wagner. Uber eine eigenschaft der ebenen komplex. In Math. Ann., volume 114, pages 570-590, 1937. Google Scholar
  35. Hassler Whitney. Non-separable and planar graphs. Transactions of the American Mathematical Society, 34:339-362, 1932. URL: https://doi.org/10.1090/S0002-9947-1932-1501641-2.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact