Document Open Access Logo

Testability and Local Certification of Monotone Properties in Minor-Closed Classes

Authors Louis Esperet , Sergey Norin

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2022.58.pdf
  • Filesize: 0.73 MB
  • 15 pages

Document Identifiers

Author Details

Louis Esperet
  • Univ. Grenoble Alpes, CNRS, Laboratoire G-SCOP, Grenoble, France
Sergey Norin
  • Department of Mathematics and Statistics, McGill University, Montreal, Canada

Funding

  • Esperet, Louis: supported by the French ANR Projects GATO (ANR-16-CE40-0009-01), GrR (ANR-18-CE40-0032), TWIN-WIDTH (ANR-21-CE48-0014-01), and by LabEx PERSYVAL-lab (ANR-11-LABX-0025).
  • Norin, Sergey: supported by an NSERC Discovery grant.

Acknowledgements

This work was initiated during the Graph Theory workshop in Oberwolfach, Germany, in January 2022. The authors would like to thank the organizers and participants for all the discussions and nice atmosphere (and in particular Gwenaël Joret, Chun-Hung Liu, and Ken-ichi Kawarabayashi for the discussions related to the topic of this paper). The authors would also like to thank Gábor Elek for his remarks on an earlier version of this manuscript, and his suggestion to replace minor-closed classes by classes of bounded asymptotic dimension in Theorem 4.

Cite AsGet BibTex

Louis Esperet and Sergey Norin. Testability and Local Certification of Monotone Properties in Minor-Closed Classes. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 58:1-58:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ICALP.2022.58

Abstract

The main problem in the area of graph property testing is to understand which graph properties are testable, which means that with constantly many queries to any input graph G, a tester can decide with good probability whether G satisfies the property, or is far from satisfying the property. Testable properties are well understood in the dense model and in the bounded degree model, but little is known in sparse graph classes when graphs are allowed to have unbounded degree. This is the setting of the sparse model. We prove that for any proper minor-closed class 𝒢, any monotone property (i.e., any property that is closed under taking subgraphs) is testable for graphs from 𝒢 in the sparse model. This extends a result of Czumaj and Sohler (FOCS'19), who proved it for monotone properties with finitely many forbidden subgraphs. Our result implies for instance that for any integers k and t, k-colorability of K_t-minor free graphs is testable in the sparse model. Elek recently proved that monotone properties of bounded degree graphs from minor-closed classes that are closed under disjoint union can be verified by an approximate proof labeling scheme in constant time. We show again that the assumption of bounded degree can be omitted in his result.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
  • Theory of computation → Streaming, sublinear and near linear time algorithms
Keywords
  • Property testing
  • sparse model
  • local certification
  • minor-closed classes

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. The local detection paradigm and its application to self-stabilization. Theoretical Computer Science, 186(1-2):199-229, 1997. URL: https://doi.org/10.1016/S0304-3975(96)00286-1.
  2. Noga Alon, Richard A. Duke, Hanno Lefmann, Vojtech Rödl, and Raphael Yuster. The algorithmic aspects of the regularity lemma. Journal of Algorithms, 16(1):80-109, 1994. URL: https://doi.org/10.1006/jagm.1994.1005.
  3. Noga Alon, Eldar Fischer, Ilan Newman, and Asaf Shapira. A combinatorial characterization of the testable graph properties: It’s all about regularity. SIAM Journal on Computing, 39(1):143-167, 2009. URL: https://doi.org/10.1137/060667177.
  4. Noga Alon and Asaf Shapira. A characterization of the (natural) graph properties testable with one-sided error. SIAM Journal on Computing, 37(6):1703-1727, 2008. URL: https://doi.org/10.1137/06064888X.
  5. Noga Alon and Asaf Shapira. Every monotone graph property is testable. SIAM Journal on Computing, 38(2):505-522, 2008. URL: https://doi.org/10.1137/050633445.
  6. Baruch Awerbuch, Boaz Patt-Shamir, and George Varghese. Self-stabilization by local checking and correction (extended abstract). In 32nd Annual Symposium on Foundations of Computer Science, San Juan, Puerto Rico, 1-4 October 1991, pages 268-277. IEEE Computer Society, 1991. URL: https://doi.org/10.1109/SFCS.1991.185378.
  7. Sabyasachi Basu, Akash Kumar, and C. Seshadhri. The complexity of testing all properties of planar graphs, and the role of isomorphism. In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022, pages 1702-1714. SIAM, 2022. URL: https://doi.org/10.1137/1.9781611977073.69.
  8. Itai Benjamini, Oded Schramm, and Asaf Shapira. Every minor-closed property of sparse graphs is testable. Advances in Mathematics, 223(6):2200-2218, 2010. Google Scholar
  9. Marthe Bonamy, Nicolas Bousquet, Louis Esperet, Carla Groenland, Chun-Hung Liu, François Pirot, and Alex D. Scott. Asymptotic dimension of minor-closed families and Assouad-Nagata dimension of surfaces. Journal of the European Mathematical Society, to appear. URL: http://arxiv.org/abs/2012.02435.
  10. 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.
  11. Nicolas Bousquet, Laurent Feuilloley, and Théo Pierron. What can be certified compactly? CoRR, abs/2202.06065, 2022. URL: http://arxiv.org/abs/2202.06065.
  12. Nikolay Brodskiy, Jerzy Dydak, Michael Levin, and Atish Mitra. A Hurewicz theorem for the Assouad-Nagata dimension. Journal of the London Mathematical Society, 77(3):741-756, 2008. Google Scholar
  13. 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.
  14. Artur Czumaj, Morteza Monemizadeh, Krzysztof Onak, and Christian Sohler. Planar graphs: Random walks and bipartiteness testing. Random Structures & Algorithms, 55(1):104-124, 2019. URL: https://doi.org/10.1002/rsa.20826.
  15. Artur Czumaj, Asaf Shapira, and Christian Sohler. Testing hereditary properties of nonexpanding bounded-degree graphs. SIAM Journal on Computing, 38(6):2499-2510, 2009. URL: https://doi.org/10.1137/070681831.
  16. Artur Czumaj and Christian Sohler. A characterization of graph properties testable for general planar graphs with one-sided error (it’s all about forbidden subgraphs). In David Zuckerman, editor, 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 1525-1548. IEEE Computer Society, 2019. URL: https://doi.org/10.1109/FOCS.2019.00089.
  17. Matt DeVos, Guoli Ding, Bogdan Oporowski, Daniel P. Sanders, Bruce A. Reed, Paul D. Seymour, and Dirk Vertigan. Excluding any graph as a minor allows a low tree-width 2-coloring. Journal of Combinatorial Theory, Series B, 91(1):25-41, 2004. URL: https://doi.org/10.1016/j.jctb.2003.09.001.
  18. Vida Dujmović, Pat Morin, and David R. Wood. Layered separators in minor-closed graph classes with applications. Journal of Combinatorial Theory, Series B, 127:111-147, 2017. URL: https://doi.org/10.1016/j.jctb.2017.05.006.
  19. Vida Dujmović, Pat Morin, and David R. Wood. Graph product structure for non-minor-closed classes. CoRR, abs/1907.05168, 2019. URL: http://arxiv.org/abs/1907.05168.
  20. Zdeněk Dvořák and Jean-Sébastien Sereni. On fractional fragility rates of graph classes. Electronic Journal of Combinatorics, 27(4):P4.9, 2020. URL: https://www.combinatorics.org/ojs/index.php/eljc/article/view/v27i4p9.
  21. Gábor Elek. Planarity can be verified by an approximate proof labeling scheme in constant time. CoRR, abs/2006.11869, 2020. URL: http://arxiv.org/abs/2006.11869.
  22. 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.
  23. Laurent Feuilloley. Introduction to local certification. Discrete Mathematics & Theoretical Computer Science, 23(3), 2021. URL: http://arxiv.org/abs/1910.12747.
  24. 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. URL: http://arxiv.org/abs/2007.08084.
  25. 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.
  26. Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, and Ioan Todinca. A meta-theorem for distributed certification. CoRR, abs/2112.03195, 2021. URL: http://arxiv.org/abs/2112.03195.
  27. Oded Goldreich. Introduction to Property Testing. Cambridge University Press, 2017. URL: https://doi.org/10.1017/9781108135252.
  28. Oded Goldreich, Shafi Goldwasser, and Dana Ron. Property testing and its connection to learning and approximation. Journal of the ACM, 45(4):653-750, 1998. URL: https://doi.org/10.1145/285055.285060.
  29. Oded Goldreich and Dana Ron. Property testing in bounded degree graphs. Algorithmica, 32(2):302-343, 2002. URL: https://doi.org/10.1007/s00453-001-0078-7.
  30. 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.
  31. Mikhael Gromov. Asymptotic invariants of infinite groups, in Geometric Group Theory, Volume 2, volume 182 of London Mathematical Society Lecture Note Series. Cambridge University Press, 1993. Google Scholar
  32. Avinatan Hassidim, Jonathan A. Kelner, Huy N. Nguyen, and Krzysztof Onak. Local graph partitions for approximation and testing. In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, October 25-27, 2009, Atlanta, Georgia, USA, pages 22-31. IEEE Computer Society, 2009. URL: https://doi.org/10.1109/FOCS.2009.77.
  33. D Hume. A continuum of expanders. Fundamenta Mathematicae, 238:143-152, 2017. Google Scholar
  34. Gene Itkis and Leonid A. Levin. Fast and lean self-stabilizing asynchronous protocols. In 35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mexico, USA, 20-22 November 1994, pages 226-239. IEEE Computer Society, 1994. URL: https://doi.org/10.1109/SFCS.1994.365691.
  35. Wolfgang Mader. Homomorphieeigenschaften und mittlere Kantendichte von Graphen. Mathematische Annalen, 174(4):265-268, 1967. Google Scholar
  36. Jaroslav Nešetřil and Patrice Ossona de Mendez. Sparsity - Graphs, Structures, and Algorithms, volume 28 of Algorithms and combinatorics. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-27875-4.
  37. Ilan Newman and Christian Sohler. Every property of hyperfinite graphs is testable. SIAM Journal on Computing, 42(3):1095-1112, 2013. URL: https://doi.org/10.1137/120890946.
  38. Mikhail I. Ostrovskii and David Rosenthal. Metric dimensions of minor excluded graphs and minor exclusion in groups. International Journal of Algebra and Computation, 25(4):541-554, 2015. Google Scholar
  39. Farhad Shahrokhi. New representation results for planar graphs. In 29th European Workshop on Computational Geometry EuroCG, pages 177-180, 2013. URL: http://arxiv.org/abs/1502.06175.
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