Fixed-parameter tractability of first-order model checking on monadically dependent classes
Fixed-parameter tractability of first-order model checking on monadically dependent classes
A graph class is monadically dependent if it has the model-theoretic property described in the survey. For a graph , let denote its size, and let denote first-order logic.
The monadic dependence model-checking conjecture. For every monadically dependent class there is a constant and an algorithm that, given a graph and an sentence , decides whether in time .
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.