{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-05","reactions":{}}