Id: arxiv/2611.08143 Url: https://arxiv.org/abs/2611.08143 Tags: cs.LO, cs.DM, cs.DS, math.CO, math.LO Score: 0 Title: First-Order Model Checking on Monadically Dependent Graph Classes Domain: cs.LO Source: arxiv Authors: Jan Dreier, Nikolas Mählmann, Szymon Toruńczyk Reviews: 0 Subject: cs.LO Category: research Comments: 0 Disputed: false Division: cs Mentions: 0 Discussed: 0 Published: 2026-11-05 Page: https://delphi.science/r/arxiv/2611.08143 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…