First-Order Model Checking on Monadically Dependent Graph Classes
cs.LO, cs.DM, cs.DS, math.CO, math.LO
Submitted: 2026-11-05
Updated: 2026-11-05
License: http://creativecommons.org/licenses/by/4.0/
The gist: Monadically dependent graph classes are those in which first-order logic cannot encode all graphs.
Terminology
Abstract
Monadically dependent graph classes are those in which first-order logic cannot encode all graphs. They include all nowhere dense classes and all classes of bounded twin-width. We show that first-order model checking is fixed-parameter tractable on every monadically dependent graph class. Together with the known hardness result for hereditary classes that are not monadically dependent, this gives a complete characterization of the hereditary graph classes with fixed-parameter tractable first-order model checking. This resolves a central open problem in algorithmic model theory. Our proof combines ideas from structural graph theory (graph decompositions), finite model theory (locality of first-order logic), and model theory (counting types). In particular, we show that in monadically dependent classes, tuples of fixed length have only U O(1) types of fixed quantifier rank over any set of parameters U.
Sources
- Decomposition horizons and a characterization of stable hereditary classes of graphs
- Flip-Breakability: A Combinatorial Dichotomy for Monadically Dependent Graph Classes
- Variants of Merge-Width and Applications
- Flips and Merge-Width in Sparse Graphs
- Neighborhood Complexity and Radius-1 Merge-Width in Monadically Dependent Graph Classes
- Merge-width and First-Order Model Checking
- A Rank-Preserving Locality Theorem
- Flipper games for monadically stable graph classes
- On the number of types in sparse graphs
- Ordered graphs of bounded twin-width
- Flip-width: Cops and Robber on dense graphs
Related papers
- A Non-Dichotomy for CSPs of Stable omega-Categorical Structures
- A Deeper Look at Depth: Stable Generation Accounting for Quantifier Reasoning
- Formalizing Hyperspaces and Operations on Subsets of Polish Spaces over Abstract Exact Real Numbers
- A Diagrammatic Basis for Computer Programming
- Interpolation via Generalized Splitting
- Staying Productive Under the Palm Trees: On Graded Coeffect Typing in the Tropical Semiring