First-order model checking is efficient on monadically dependent graphs
First-Order Model Checking on Monadically Dependent Graph Classes
Logic in Computer ScienceDiscrete MathematicsData Structures and Algorithms
Summary
Some graphs are easier to analyze with logical rules than others. The authors found a clear boundary between types of graphs where checking certain conditions quickly is possible, and where it is hard. They showed that a large and important class of graphs called monadically dependent graphs can be handled efficiently by first-order model checking. This answers a long-standing question about which graph classes allow quick logical queries.
What this means in practice
- •For graph algorithm designers: Design algorithms to efficiently check logical properties on large structured graph datasets identified as monadically dependent.
- •For database system developers: Optimize query engines for graph databases by exploiting fixed-parameter tractable model checking on classes of graphs with bounded structural complexity.
A theory result. No direct application yet.
Authors
Jan Dreier, Nikolas Mählmann, Szymon Toruńczyk
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$.