A Logic-based Algorithmic Meta-Theorem for Treedepth: Single Exponential FPT Time and Polynomial Space

arXiv:2510.19793 · cs.DS, cs.LO · Submitted 2025-10-22 · Read on arXiv

cs.DS, cs.LO

Submitted: 2025-10-22

Updated: 2026-10-28

Comments: Accepted at SODA 2026

License: http://creativecommons.org/licenses/by/4.0/

The gist: For a graph G, the parameter treedepth measures the minimum depth among all forests F, called elimination forests, such that G is a subgraph of the ancestor-descendant closure of F.

Terminology

Abstract

For a graph G, the parameter treedepth measures the minimum depth among all forests F, called elimination forests, such that G is a subgraph of the ancestor-descendant closure of F. We introduce a logic, called neighborhood operator logic with acyclicity, connectivity and clique constraints (2[]+ for short), that captures all NP-hard problems like Independent Set or Hamiltonian Cycle that are known to be tractable in time 2 O(k)n O(1) and space n O(1) on n-vertex graphs provided with elimination forests of depth k. We provide a model checking algorithm for 2[]+ with such complexity that unifies and extends these results. For 2[]+, the fragment of the above logic that does not use acyclicity and connectivity constraints, we get a strengthening of this result, where the space complexity is reduced to O(k (n)). With a similar mechanism as the distance neighborhood logic introduced in [Bergougnoux, Dreier and Jaffke, SODA 2023], the logic 2[]+ is an extension of the fully-existential 2 with predicates for (1) querying generalizations of the neighborhoods of vertex sets, (2) verifying the connectivity and acyclicity of vertex and edge sets, and (3) verifying that a vertex set induces a clique. Our results provide 2 O(k)n O(1) time and n O(1) space algorithms for problems for which the existence of such algorithms was previously unknown. In particular, 2[] captures CNF-SAT via the incidence graphs associated to CNF formulas, and it also captures several modulo counting problems like Odd Dominating Set.

Sources

Related papers