A Uniform Algorithm for Strict NP on Bounded-Treedepth StructuresResearch Paper
Strict NP (SNP) is the class of properties of finite structures expressible as with quantifier-free. It contains many graph-layout and colouring problems: deciding whether the stack number, queue number or track number of a graph is at most , whether its twin-width is at most , or whether it is -colour…