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

About 5 years old · traced to

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(φ)⋅∣G∣cf(\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.

References

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.