Preprint
Oct 2026
A Uniform Algorithm for Strict NP on Bounded-Treedepth Graphs
A classical well-quasi-ordering result guarantees the existence of non-uniform linear-time algorithms for all problems in Strict NP on relational structures of bounded treedepth; however, this provides neither a procedure for constructing these algorithms nor computable bounds on their parameter dependence. We turn thi...
Thomas Depian, Robert Ganian, Jakob Greilhuber et al.
· 0 citations