The monadic dependence characterization of fixed-parameter tractable FO model checking

Let d4a2d4a2 be a hereditary class of structures. FO model checking asks, given a first-order sentence d719d719 and a structure in d4a2d4a2, whether d719d719 holds in that structure. The class d4a2d4a2 is monadically dependent if it does not interpret every finite graph via first-order formulas with a bounded number of added unary predicates.

The monadic dependence conjecture. For every hereditary class d4a2d4a2 of structures, FO model checking is FPT on d4a2d4a2 if and only if d4a2d4a2 is monadically dependent.

This would characterize the hereditary classes admitting fixed-parameter tractable first-order model checking in model-theoretic terms. The source presents it as an existing conjecture, and no resolution is given here.

Sources & referencesView supporting material

Primary source

Édouard Bonnet, Dibyayan Chakraborty, Eun Jung Kim, Noleen Köhler, Raul Lopes and Stéphan Thomassé, “Twin-width VIII: delineation and win-wins”, arXiv:2204.00722 (2022).

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.