2026-07-25T13:34:21Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18696 2024-03-06T11:02:29Z ddc:004 open_access

Evaluating Restricted First-Order Counting Properties on Nowhere Dense Classes and Beyond Dreier, Jan Mock, Daniel Rossmanith, Peter nowhere dense sparsity counting logic dominating set FPT 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jan Dreier and Daniel Mock and Peter Rossmanith 2023 Is Part Of LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2023.43 urn:nbn:de:0030-drops-186961 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.43 eng https://creativecommons.org/licenses/by/4.0/legalcode