Fixed-parameter tractability conjecture for first-order model checking on hereditary classes
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.
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
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.