Fixed-parameter tractability conjecture for first-order model checking on hereditary classes

Let C\mathscr C be a hereditary class of structures. A class is monadically NIP if it remains NIP after arbitrary unary predicates are added. Hereditary first-order model-checking conjecture. First-order model checking is fixed-parameter tractable on C\mathscr C if and only if C\mathscr C is monadically NIP. Here fixed-parameter tractability means an algorithm with running time f(φ)Gcf(\varphi)\cdot |G|^c for some computable function ff and constant cc. The conjecture would characterize exactly the hereditary classes admitting tractable first-order model checking; the paper notes that all currently known tractable hereditary classes are monadically NIP, while the converse is not established in general.

Sources & referencesView supporting material

Primary source

Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, Pierre Simon, Stéphan Thomassé and Szymon Toruńczyk, “Twin-width IV: ordered graphs and matrices”, arXiv:2102.03117 (2021).

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.