Nothing Special   »   [go: up one dir, main page]
Document Open Access Logo

Local Certification of Geometric Graph Classes

Authors Oscar Defrain , Louis Esperet , Aurélie Lagoutte , Pat Morin , Jean-Florent Raymond

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2024.48.pdf
  • Filesize: 0.8 MB
  • 14 pages

Document Identifiers

Author Details

Oscar Defrain
  • Aix Marseille Université, CNRS, LIS, Marseille, France
Louis Esperet
  • Laboratoire G-SCOP (CNRS, Univ. Grenoble Alpes), Grenoble, France
Aurélie Lagoutte
  • Laboratoire G-SCOP (CNRS, Univ. Grenoble Alpes), Grenoble, France
Pat Morin
  • School of Computer Science, Carleton University, Canada
Jean-Florent Raymond
  • CNRS, LIP, ENS de Lyon, France

Funding

  • Esperet, Louis: partially supported by the French ANR Project TWIN-WIDTH (ANR-21-CE48-0014-01), and by LabEx PERSYVAL-lab (ANR-11-LABX-0025).
  • Lagoutte, Aurélie: partially supported by French ANR project GRALMECO (ANR-21-CE48-0004).
  • Morin, Pat: partially supported by NSERC.
  • Raymond, Jean-Florent: partially supported by French ANR project GRALMECO (ANR-21-CE48-0004).

Cite AsGet BibTex

Oscar Defrain, Louis Esperet, Aurélie Lagoutte, Pat Morin, and Jean-Florent Raymond. Local Certification of Geometric Graph Classes. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 48:1-48:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
https://doi.org/10.4230/LIPIcs.MFCS.2024.48

Abstract

The goal of local certification is to locally convince the vertices of a graph G that G satisfies a given property. A prover assigns short certificates to the vertices of the graph, then the vertices are allowed to check their certificates and the certificates of their neighbors, and based only on this local view and their own unique identifier, they must decide whether G satisfies the given property. If the graph indeed satisfies the property, all vertices must accept the instance, and otherwise at least one vertex must reject the instance (for any possible assignment of certificates). The goal is to minimize the size of the certificates. In this paper we study the local certification of geometric and topological graph classes. While it is known that in n-vertex graphs, planarity can be certified locally with certificates of size O(log n), we show that several closely related graph classes require certificates of size Ω(n). This includes penny graphs, unit-distance graphs, (induced) subgraphs of the square grid, 1-planar graphs, and unit-square graphs. These bounds are tight up to a constant factor and give the first known examples of hereditary (and even monotone) graph classes for which the certificates must have linear size. For unit-disk graphs we obtain a lower bound of Ω(n^{1-δ}) for any δ > 0 on the size of the certificates, and an upper bound of O(n log n). The lower bounds are obtained by proving rigidity properties of the considered graphs, which might be of independent interest.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph theory
  • Computing methodologies → Distributed computing methodologies
  • Theory of computation → Computational geometry
Keywords
  • Local certification
  • proof labeling schemes
  • geometric intersection graphs

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Noga Alon and Andrey Kupavskii. Two notions of unit distance graphs. Journal of Combinatorial Theory, Series A, 125:1-17, 2014. Google Scholar
  2. Nicolas Bousquet, Laurent Feuilloley, and Théo Pierron. Local certification of graph decompositions and applications to minor-free classes. In Quentin Bramas, Vincent Gramoli, and Alessia Milani, editors, 25th International Conference on Principles of Distributed Systems, OPODIS 2021, December 13-15, 2021, Strasbourg, France, volume 217 of LIPIcs, pages 22:1-22:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.OPODIS.2021.22.
  3. Keren Censor-Hillel, Ami Paz, and Mor Perry. Approximate proof-labeling schemes. Theoretical Computer Science, 811:112-124, 2020. URL: https://doi.org/10.1016/j.tcs.2018.08.020.
  4. Pierluigi Crescenzi, Pierre Fraigniaud, and Ami Paz. Trade-offs in distributed interactive proofs. In Jukka Suomela, editor, 33rd International Symposium on Distributed Computing, DISC 2019, October 14-18, 2019, Budapest, Hungary, volume 146 of LIPIcs, pages 13:1-13:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPICS.DISC.2019.13.
  5. Oscar Defrain, Louis Esperet, Aurélie Lagoutte, Pat Morin, and Jean-Florent Raymond. Local certification of geometric graph classes. CoRR, abs/2311.16953, 2023. https://arxiv.org/abs/2311.16953, URL: https://doi.org/10.48550/arXiv.2311.16953.
  6. Louis Esperet and Benjamin Lévêque. Local certification of graphs on surfaces. Theoretical Computer Science, 909:68-75, 2022. URL: https://doi.org/10.1016/j.tcs.2022.01.023.
  7. Laurent Feuilloley. Introduction to local certification. Discrete Mathematics & Theoretical Computer Science, 23(3), 2021. URL: https://arxiv.org/abs/1910.12747.
  8. Laurent Feuilloley, Nicolas Bousquet, and Théo Pierron. What can be certified compactly? Compact local certification of MSO properties in tree-like graphs. In Alessia Milani and Philipp Woelfel, editors, PODC '22: ACM Symposium on Principles of Distributed Computing, Salerno, Italy, July 25 - 29, 2022, pages 131-140. ACM, 2022. URL: https://doi.org/10.1145/3519270.3538416.
  9. Laurent Feuilloley, Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, Éric Rémila, and Ioan Todinca. Compact distributed certification of planar graphs. Algorithmica, 83(7):2215-2244, 2021. URL: https://doi.org/10.1007/s00453-021-00823-w.
  10. Laurent Feuilloley, Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, Éric Rémila, and Ioan Todinca. Local certification of graphs with bounded genus. Discrete Applied Mathematics, 325:9-36, 2023. URL: https://doi.org/10.1016/j.dam.2022.10.004.
  11. Pierre Fraigniaud, Frédéric Mazoit, Pedro Montealegre, Ivan Rapaport, and Ioan Todinca. Distributed certification for classes of dense graphs. arXiv preprint, 2023. URL: https://arxiv.org/abs/2307.14292.
  12. Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, and Ioan Todinca. A meta-theorem for distributed certification. In Merav Parter, editor, Structural Information and Communication Complexity - 29th International Colloquium, SIROCCO 2022, Paderborn, Germany, June 27-29, 2022, Proceedings, volume 13298 of Lecture Notes in Computer Science, pages 116-134. Springer, 2022. URL: https://doi.org/10.1007/978-3-031-09993-9_7.
  13. Mika Göös and Jukka Suomela. Locally checkable proofs in distributed computing. Theory of Computing, 12(1):1-33, 2016. URL: https://doi.org/10.4086/toc.2016.v012a019.
  14. Benjamin Jauregui, Pedro Montealegre, Diego Ramírez-Romero, and Ivan Rapaport. Local certification of some geometric intersection graph classes. CoRR, abs/2309.04789, 2023. URL: https://doi.org/10.48550/arXiv.2309.04789.
  15. Benjamin Jauregui, Pedro Montealegre, and Ivan Rapaport. Distributed interactive proofs for the recognition of some geometric intersection graph classes. In Merav Parter, editor, Structural Information and Communication Complexity - 29th International Colloquium, SIROCCO 2022, Paderborn, Germany, June 27-29, 2022, Proceedings, volume 13298 of Lecture Notes in Computer Science, pages 212-233. Springer, 2022. URL: https://doi.org/10.1007/978-3-031-09993-9_12.
  16. Gillat Kol, Rotem Oshman, and Raghuvansh R. Saxena. Interactive distributed proofs. In Calvin Newport and Idit Keidar, editors, Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC 2018, Egham, United Kingdom, July 23-27, 2018, pages 255-264. ACM, 2018. URL: https://dl.acm.org/citation.cfm?id=3212771.
  17. 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.
  18. Colin McDiarmid and Tobias Müller. The number of disk graphs. European Journal of Combinatorics, 35:413-431, 2014. Selected Papers of EuroComb'11. URL: https://doi.org/10.1016/j.ejc.2013.06.037.
  19. Moni Naor, Merav Parter, and Eylon Yogev. The power of distributed verifiers in interactive proofs. In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 1096-115. SIAM, 2020. URL: https://doi.org/10.1137/1.9781611975994.67.
  20. Jaroslav Nešetřil and Patrice Ossona De Mendez. Sparsity: graphs, structures, and algorithms, volume 28. Springer Science & Business Media, 2012. Google Scholar
  21. Neil Robertson and Paul D. Seymour. Graph minors. XX. Wagner’s conjecture. Journal of Combinatorial Theory, Series B, 92(2):325-357, 2004. URL: https://doi.org/10.1016/j.jctb.2004.08.001.
  22. Hassler Whitney. 2-isomorphic graphs. American Journal of Mathematics, 55(1):245-254, 1933. Google Scholar
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