FPT FO model checking superclass of twin-width

Question (common superclass for FPT FO model checking) · arXiv:2004.14789

arXiv Question medium confidence— first stated 2021-10-25

Authors: Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, Rémi Watrigant

Status partial high confidence

The natural candidate common superclass — monadically NIP (monadically dependent) classes — has been identified in the literature and is known to contain both bounded twin-width and nowhere dense classes. Significant partial progress has been made: FPT FO model checking was proved for all monadically stable graph classes (which strictly contain all nowhere dense classes) in 2023, and for all classes of bounded merge-width (which unify bounded twin-width and bounded expansion) in 2025. The full question of whether all monadically NIP/dependent classes admit FPT FO model checking remains an open conjecture, widely regarded as the central problem in the area.

Cited literature (2)

partial First-Order Model Checking on Monadically Stable Graph Classes (2023)

Jan Dreier et al. · arXiv preprint · arXiv:2311.18740

Proves FPT FO model checking for all monadically stable graph classes, a strict superclass of nowhere dense that does not subsume bounded twin-width, extending one half of the question.
partial Merge-width and First-Order Model Checking (2025)

Jan Dreier, Szymon Toruńczyk · arXiv preprint · arXiv:2502.18065

Introduces merge-width, a parameter whose bounded classes subsume both bounded expansion and bounded twin-width, and proves FPT FO model checking for all classes of bounded merge-width, giving a unified common superclass for the algorithmic part of the question.

Reviewer notes. Monadically NIP (= monadically dependent) is the broadly accepted natural candidate for the common superclass asked about: it contains both bounded twin-width and nowhere dense classes, and the conjecture that FPT FO model checking holds exactly on monadically NIP hereditary classes is the central open problem in parameterized model checking. The two papers cited give FPT for important proper sub-cases: monadically stable (⊇ nowhere dense, published as arXiv:2311.18740) and bounded merge-width (⊇ bounded twin-width ∪ bounded expansion, published as arXiv:2502.18065 and appearing at STOC 2025). The question is therefore partially resolved: a natural common superclass with FPT is known (bounded merge-width), and evidence strongly points to monadically NIP as the tight characterisation, but the full statement for all monadically NIP classes is open.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Question. Do bounded twin-width and nowhere dense classes admit a natural common superclass still admitting an FPT algorithm for FO model checking?

Context

Figure 3 shows that bounded twin-width and nowhere dense classes together roughly subsume all current knowledge on fixed-parameter tractability of FO model checking. The authors explicitly pose whether a natural common superclass of both still admits an FPT algorithm for FO model checking.

Notes. Posed as a rhetorical question in the caption of Figure 3, not in a labelled theorem environment.

Source paper

Twin-width I: tractable FO model checking
Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, Rémi Watrigant · 2021-10-25
https://arxiv.org/abs/2004.14789 PDF source