UNISTRUC: Unifying the Structural Foundations of Tractability

• Applicant: Dr. Jan Dreier
• Subject Area: Theoretical Computer Science
• Term: since 2026
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 563448077

WIDER RESEARCH CONTEXT: Addressing algorithmic problems that are hard under worst-case complexity is a central challenge in computer science. The aim of this project is to identify and characterize in a foundational manner well-behaved input instances on which many of these hard algorithmic problems become tractable. Nešetřil and Ossona de Mendez introduced the notion of nowhere dense graph classes, which form the foundation of their systematic theory on sparsity of graph classes. This very general notion encompasses, for example, planar graphs and graphs with bounded degree or excluded minor. A breakthrough result by Grohe, Kreutzer and Siebertz showed that nowhere dense classes are algorithmically tractable in the sense that all problems expressible in first-order logic can be solved in almost-linear time on nowhere dense graph classes. We recently extended this result to monadically stable graph classes, a powerful notion from model theory that goes beyond classical sparsity theory. Recently, classes of bounded twin-width have obtained considerable attention. These classes incomparable to monadically stable and nowhere dense classes, but algorithmically tractable in a similar sense. In summary, there has been a long quest of identifying larger and larger algorithmically tractable graph classes, and bounded twin-width and monadically stable classes form the current frontier of tractability. RESEARCH QUESTIONS: Twin-width and monadic stability are two fundamentally incompatible notions. I want to unify and generalize the two corresponding theories into a single theory of algorithmic tractability that exactly characterizes all tractable (hereditary) graph classes. As a cornerstone, I want to show that first-order model checking is fixed parameter tractable on monadically dependent graph classes. METHODS: The project will combine techniques from sparsity theory, finite model theory, stability theory, and twin-width theory to discover useful combinatorial structure in well-behaved graphs. This, in turn, will be used to compute algorithmically useful decompositions. In particular, I aim to build upon Ramsey-like properties like Uniform Quasi-Wideness, flip-flatness or flip-breakability, pursuit-evasion games such as the Flipper game or the flip-width game, and the model checking methods for nowhere dense and monadically stable graph classes. INNOVATION: The planned project aims to unify and extend the core results of the highly influential sparsity theory, twin-width theory and stability theory. The result would have a strong impact on various areas of theoretical computer science, in particular computational logic, graph theory, and parameterized complexity.

• DFG Programme: Emmy Noether Independent Research Groups