Fixed-parameter tractability conjecture for first-order model checking on hereditary classes
Let 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 if and only if is monadically NIP. Here fixed-parameter tractability means an algorithm with running time for some computable function and constant . 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
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.