A Logic-based Algorithmic Meta-Theorem for Treedepth: Single Exponential FPT Time and Polynomial Space
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
- Treedepth Inapproximability and Exponential ETH Lower Bound
- The Price of Being Partial: Complexity of Partial Generalized Dominating Set on Bounded-Treewidth Graphs
- Graph classes through the lens of logic
Related papers
- PHastR: Faster Minimal Perfect Hashing with Rotated Layouts
- Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with k-SUM in 2D
- Polynomial-time computation of p-contraction fixed points for even p
- Separations Between Submodular-Like Graph Widths
- Bounded Integer Programming in Almost N 2d Time
- Fast Odd-Permutation Sums in Characteristic Two and Shortest Even Directed Cycles