Pilipczuk–Toruńczyk's rank conjecture for elementarily-fpt model checking
Pilipczuk–Toruńczyk's rank conjecture for elementarily-fpt model checking
Let be a hereditary graph class. For , let denote the class of all trees of depth . Pilipczuk–Toruńczyk's rank conjecture. The class has elementarily fixed-parameter tractable model checking if and only if there is some such that does not transduce . The conjecture would characterize hereditary classes with elementarily-fpt first-order model checking by bounded rank. The source notes that the conjecture motivates the paper and remains a subject of future work; its status is not resolved there.
Sources & referencesView supporting material
Primary source
Jakub Gajarský, Michał Pilipczuk, Marek Sokołowski, Giannos Stamoulis and Szymon Toruńczyk, “Elementary first-order model checking for sparse graphs”, arXiv:2401.16230 (2025).
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.