Fixed-parameter tractability of first-order model checking on monadically dependent classes

A graph class C\mathscr{C} is monadically dependent if it has the model-theoretic property described in the survey. For a graph GG, let nn denote its size, and let FO\mathsf{FO} denote first-order logic.

The monadic dependence model-checking conjecture. For every monadically dependent class C\mathscr{C} there is a constant cNc\in\mathbb N and an algorithm that, given a graph GCG\in\mathscr{C} and an FO\mathsf{FO} sentence φ\varphi, decides whether GφG\models\varphi in time OC,φ(nc)\mathcal{O}_{\mathscr{C},\varphi}(n^c).

This conjecture would extend the fixed-parameter tractability of first-order model checking from nowhere dense classes to all monadically dependent classes. The survey identifies it as a main algorithmic goal and states that it remains open.

Sources & referencesView supporting material

Primary source

Michał Pilipczuk, “Graph classes through the lens of logic”, arXiv:2501.04166 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.