Can a uniform algorithm decide Strict NP on bounded-treedepth graphs with computable bounds?

The old result promised algorithms but could not build them

For graphs of bounded treedepth, a well-quasi-ordering under induced subgraphs guarantees that every problem in Strict NP has a linear-time algorithm. That guarantee is real but thin. It says an algorithm exists for each fixed sentence and each fixed treedepth bound, yet it supplies no procedure for constructing the algorithm from the sentence and the bound, no computable bound on how the running time depends on those two inputs, and no way to output the witness relations that make a positive instance positive.

In parameterized complexity terms, such algorithms are non-uniform fixed-parameter algorithms. They are not fixed-parameter algorithms in the usual sense, because fixed-parameter tractability requires the dependence on formula length and treedepth to be bounded by a computable function. The paper's target is exactly this gap: convert the existential statement into one algorithm that works for all Strict NP sentences at once.

One algorithm covers every Strict NP sentence

The main result, stated in simplified form as Theorem A, is an algorithm A that takes a Strict NP sentence φ and a relational structure R, decides whether R ⊨ φ, and runs in time f(|φ|, td(R)) · |R| for some computable function f. Here |R| is the encoding size of the input structure, td(R) is the treedepth of its Gaifman graph, and the polynomial degree does not depend on φ.

Two features distinguish this from the earlier guarantee. First, the algorithm is uniform: a single procedure handles all sentences, rather than a separate unspecified algorithm per sentence and bound. Second, it is constructive and does not require a forbidden-substructure characterization as part of the input. The Gaifman graph detail matters because treedepth is not read off the input relations directly; it is measured on the graph whose vertices are the elements and whose edges join elements that co-occur in a tuple of an input relation.

Witnesses cost more than a yes-or-no decision

Deciding and witnessing are separate guarantees with different running times. If R ⊨ φ, the algorithm can output a witness in time f(|φ|, td(R)) · |R|^ar(φ), where ar(φ) is the maximum arity of any relation among the existentially quantified relations R1, …, Rr. The exponent therefore depends on that arity, and a witness may have size |R|^ar(φ).

This is a meaningful distinction rather than a technicality. Strict NP differs from monadic second-order logic precisely because the existentially quantified relations may have unbounded arity: a witness can contain a linear order on the whole domain or higher-arity relations describing interactions among several vertices, and witness relations may be dense even when the input structure is sparse. The finer-grained statement in the paper's Theorem 1 allows the algorithm to output any requested subset of the witness relations, with the polynomial exponent depending only on the maximum arity among those requested relations.

Pruning plus positive certificates replace the missing bound

The proof strategy starts from a pruning idea. Fix φ and a treedepth bound h. There is a finite obstruction set J(h, φ) such that a structure of treedepth at most h satisfies φ exactly when it contains no member of J(h, φ) as an induced substructure. Using types on an elimination forest, one can prune R to an induced substructure R_p whose size is bounded by a computable function g(p, h), while preserving whether R contains an induced substructure of size at most p.

If an oracle revealed the size M of the largest obstruction in J(h, φ), setting p = M would make R_p ⊨ φ equivalent to R ⊨ φ, and brute force on the bounded-size R_p would decide the instance. The catch is that M is unknown. Increasing p works for negative instances, since a finite obstruction is eventually uncovered, but positive instances have no termination criterion. The paper's key step is defining positive certificates that can be recognized on a bounded-size pruned instance and extended to the original input. The algorithm starts at a threshold depending only on φ and td(R), increases p, and for each p checks whether R_p ⊭ φ (output no) or whether R_p admits a positive certificate (output yes).

Why the running-time bound has no closed form

The function f is computable but not given in closed form. Its value depends on the size of the largest obstruction in J(h, φ), for which the paper has no explicit bound. The proof establishes computability through a concrete non-trivial procedure that constructs f and is guaranteed to terminate, without yielding a closed-form upper bound on its growth.

This is a limitation on how the result can be used quantitatively, not on its correctness. A reader comparing this metatheorem with Courcelle-style results should note that the guarantee here is uniformity and computability of the parameter dependence, not a tight or explicit runtime expression. The paper also notes that the positive certificates provide a recipe for extending a witness for R_p ⊨ φ into a witness for R ⊨ φ.

Applications settle open treedepth-parameterized questions

The metatheorem yields f(td(G)) · |V(G)|-time algorithms for computing the stack number, queue number, track number, twin-width, and boxicity of a graph G. The paper states that this resolves open questions on the fixed-parameter tractability of computing the stack number, queue number, track number, and twin-width parameterized by treedepth, all of which had been explicitly identified as open problems even in recent work.

These applications are where the uniformity claim earns its keep. The paper reports that some Strict NP problems are NP-hard on graphs of pathwidth 2, so their tractability cannot follow from metatheorems that apply to classes of bounded pathwidth, assuming P ≠ NP. That contrast with Courcelle's theorem is a property of the problems, not a shortcoming of the algorithm.

Three natural generalizations fail unless P = NP

The paper rules out three extensions. Strict NP formulas cannot be replaced with ESO formulas while keeping tractability with respect to treedepth, shown using Fagin's theorem. The result cannot be generalized to pathwidth, because there are Strict NP problems that are NP-hard on graphs of pathwidth 2. And a generalization to MaxSNP0, the natural optimization variant of Strict NP, is also ruled out.

These barriers define the boundary of the metatheorem. The relevant scope condition is treedepth measured on the Gaifman graph, together with the induced-substructure closure built into Strict NP syntax: satisfaction is preserved under taking induced substructures, which is why the obstruction argument applies. Properties that are not hereditary, such as Hamiltonian Cycle, fall outside this logic and are captured by MSO2 instead.

What to watch when applying the metatheorem

The most decision-relevant split in this paper is between deciding and witnessing. If the goal is a yes-or-no answer for a fixed Strict NP sentence on bounded-treedepth structures, the guarantee is f(|φ|, td(R)) · |R| with a polynomial degree independent of φ. If the goal is an explicit witness, the bound becomes f(|φ|, td(R)) · |R|^ar(φ), and the exponent tracks the arity of the requested witness relations.

The second split is between treedepth and pathwidth. The applications to stack number, queue number, track number, twin-width, and boxicity are parameterized by treedepth, and the paper's pathwidth-2 hardness observation shows this is not an artifact of the proof technique. A reader weighing whether the metatheorem applies to a given hereditary graph problem should check that the problem is expressible in Strict NP and that the parameter is treedepth on the Gaifman graph, not pathwidth or treewidth. The computable-but-not-closed-form f is the price of uniformity, and it is the point at which the paper's guarantee is strongest relative to the classical existential result it replaces.

Sources used in this answer