The monadic dependence characterization of fixed-parameter tractable FO model checking
The monadic dependence characterization of fixed-parameter tractable FO model checking
Let be a hereditary class of structures. FO model checking asks, given a first-order sentence and a structure in , whether holds in that structure. The class 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 of structures, FO model checking is FPT on if and only if 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
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.