Document Open Access Logo

Evaluating Restricted First-Order Counting Properties on Nowhere Dense Classes and Beyond

Authors Jan Dreier , Daniel Mock , Peter Rossmanith

PDF
Thumbnail PDF

File

LIPIcs.ESA.2023.43.pdf
  • Filesize: 0.78 MB
  • 17 pages

Document Identifiers

Author Details

Jan Dreier
  • TU Wien, Austria
Daniel Mock
  • RWTH Aachen University, Germany
Peter Rossmanith
  • RWTH Aachen University, Germany

Funding

Supported by the German Science Foundation (DFG), grant no. DFG-927/15-2.

Cite As Get BibTex

Jan Dreier, Daniel Mock, and Peter Rossmanith. Evaluating Restricted First-Order Counting Properties on Nowhere Dense Classes and Beyond. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 43:1-43:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ESA.2023.43

Abstract

It is known that first-order logic with some counting extensions can be efficiently evaluated on graph classes with bounded expansion, where depth-r minors have constant density. More precisely, the formulas are ∃ x₁… x_k#y φ(x_1,…,x_k, y) > N, where φ is an FO-formula. If φ is quantifier-free, we can extend this result to nowhere dense graph classes with an almost linear FPT run time. Lifting this result further to slightly more general graph classes, namely almost nowhere dense classes, where the size of depth-r clique minors is subpolynomial, is impossible unless FPT = W[1]. On the other hand, in almost nowhere dense classes we can approximate such counting formulas with a small additive error. Note those counting formulas are contained in FOC({>}) but not FOC₁(𝐏).
In particular, it follows that partial covering problems, such as partial dominating set, have fixed parameter algorithms on nowhere dense graph classes with almost linear running time.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
  • Theory of computation → Logic
  • Theory of computation → Computational complexity and cryptography
  • Mathematics of computing → Graph theory
Keywords
  • nowhere dense
  • sparsity
  • counting logic
  • dominating set
  • FPT

Metrics

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

Related Versions

References

  1. Omid Amini, Fedor V. Fomin, and Saket Saurabh. Implicit branching and parameterized partial cover problems. J. Comput. Syst. Sci., 77(6):1159-1171, 2011. URL: https://doi.org/10.1016/j.jcss.2010.12.002.
  2. Richard Beigel, Lance Fortnow, and Frank Stephan. Infinitely-often autoreducible sets. SIAM Journal on Computing, 36(3):595-608, 2006. Google Scholar
  3. Leonard Berman. On the structure of complete sets: Almost everywhere complexity and infinitely often speedup. In 17th Annual Symposium on Foundations of Computer Science (sfcs 1976), pages 76-80, 1976. URL: https://doi.org/10.1109/SFCS.1976.22.
  4. Anuj Dawar, Martin Grohe, and Stephan Kreutzer. Locally excluding a minor. In 22nd IEEE Symposium on Logic in Computer Science (LICS 2007), 10-12 July 2007, Wroclaw, Poland, Proceedings, pages 270-279. IEEE Computer Society, 2007. URL: https://doi.org/10.1109/LICS.2007.31.
  5. Anuj Dawar and Stephan Kreutzer. Domination problems in nowhere-dense classes. In Ravi Kannan and K. Narayan Kumar, editors, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2009, December 15-17, 2009, IIT Kanpur, India, volume 4 of LIPIcs, pages 157-168. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2009. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2009.2315.
  6. Rodney G. Downey and Michael R. Fellows. Parameterized Complexity. Monographs in Computer Science. Springer, 1999. URL: https://doi.org/10.1007/978-1-4612-0515-9.
  7. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. URL: https://doi.org/10.1007/978-1-4471-5559-1.
  8. Jan Dreier and Peter Rossmanith. Approximate evaluation of first-order counting queries. In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 1720-1739. SIAM, 2021. URL: https://doi.org/10.1137/1.9781611976465.104.
  9. Arnaud Durand, Nicole Schweikardt, and Luc Segoufin. Enumerating answers to first-order queries over databases of low degree. Log. Methods Comput. Sci., 18(2), 2022. URL: https://doi.org/10.46298/lmcs-18(2:7)2022.
  10. Zdenek Dvorák, Daniel Král', and Robin Thomas. Testing first-order properties for subclasses of sparse graphs. J. ACM, 60(5):36:1-36:24, 2013. URL: https://doi.org/10.1145/2499483.
  11. Markus Frick and Martin Grohe. Deciding first-order properties of locally tree-decomposable structures. J. ACM, 48(6):1184-1206, 2001. URL: https://doi.org/10.1145/504794.504798.
  12. Robert Ganian, Petr Hliněný, Alexander Langer, Jan Obdržálek, Peter Rossmanith, and Somnath Sikdar. Lower bounds on the complexity of MSO1 model-checking. Journal of Computer and System Sciences, 80(1):180-194, 2014. Google Scholar
  13. Petr A. Golovach and Yngve Villanger. Parameterized complexity for domination problems on degenerate graphs. In Hajo Broersma, Thomas Erlebach, Tom Friedetzky, and Daniël Paulusma, editors, Graph-Theoretic Concepts in Computer Science, 34th International Workshop, WG 2008, Durham, UK, June 30 - July 2, 2008. Revised Papers, volume 5344 of Lecture Notes in Computer Science, pages 195-205, 2008. URL: https://doi.org/10.1007/978-3-540-92248-3_18.
  14. Martin Grohe. Generalized model-checking problems for first-order logic. In Afonso Ferreira and Horst Reichel, editors, STACS 2001, 18th Annual Symposium on Theoretical Aspects of Computer Science, Dresden, Germany, February 15-17, 2001, Proceedings, volume 2010 of Lecture Notes in Computer Science, pages 12-26. Springer, 2001. URL: https://doi.org/10.1007/3-540-44693-1_2.
  15. Martin Grohe, Stephan Kreutzer, and Sebastian Siebertz. Deciding first-order properties of nowhere dense graphs. J. ACM, 64(3):17:1-17:32, 2017. URL: https://doi.org/10.1145/3051095.
  16. Martin Grohe and Nicole Schweikardt. First-order query evaluation with cardinality conditions. In Jan Van den Bussche and Marcelo Arenas, editors, Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, Houston, TX, USA, June 10-15, 2018, pages 253-266. ACM, 2018. URL: https://doi.org/10.1145/3196959.3196970.
  17. Henry A. Kierstead and Daqing Yang. Orderings on graphs and game coloring number. Order, 20(3):255-264, 2003. URL: https://doi.org/10.1023/B:ORDE.0000026489.93166.cb.
  18. Joachim Kneis, Daniel Mölle, and Peter Rossmanith. Partial vs. complete domination: t-dominating set. In Jan van Leeuwen, Giuseppe F. Italiano, Wiebe van der Hoek, Christoph Meinel, Harald Sack, and Frantisek Plasil, editors, SOFSEM 2007: Theory and Practice of Computer Science, 33rd Conference on Current Trends in Theory and Practice of Computer Science, Harrachov, Czech Republic, January 20-26, 2007, Proceedings, volume 4362 of Lecture Notes in Computer Science, pages 367-376. Springer, 2007. URL: https://doi.org/10.1007/978-3-540-69507-3_31.
  19. Stephan Kreutzer and Siamak Tazari. Lower bounds for the complexity of monadic second-order logic. In Proceedings of the 25th Annual IEEE Symposium on Logic in Computer Science, LICS 2010, 11-14 July 2010, Edinburgh, United Kingdom, pages 189-198. IEEE Computer Society, 2010. URL: https://doi.org/10.1109/LICS.2010.39.
  20. Dietrich Kuske and Nicole Schweikardt. First-order logic with counting. In 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2017, Reykjavik, Iceland, June 20-23, 2017, pages 1-12. IEEE Computer Society, 2017. URL: https://doi.org/10.1109/LICS.2017.8005133.
  21. 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.
  22. Jaroslav Nešetřil and Patrice Ossona de Mendez. On nowhere dense graphs. European Journal of Combinatorics, 32(4):600-617, 2011. URL: https://doi.org/10.1016/j.ejc.2011.01.006.
  23. Detlef Seese. Linear time computable problems and first-order descriptions. Math. Struct. Comput. Sci., 6(6):505-526, 1996. URL: https://doi.org/10.1017/s0960129500070079.
  24. Alexandre Vigny. Dynamic query evaluation over structures with low degree. CoRR, abs/2010.02982, 2020. URL: https://arxiv.org/abs/2010.02982.
  25. Xuding Zhu. Colouring graphs with bounded generalized colouring number. Discret. Math., 309(18):5562-5568, 2009. URL: https://doi.org/10.1016/j.disc.2008.03.024.
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 About DROPS Imprint Privacy Contact