Pilipczuk–Toruńczyk's rank conjecture for elementarily-fpt model checking

Let C C be a hereditary graph class. For dNd\in\mathbb{N}, let Td T_d denote the class of all trees of depth dd. Pilipczuk–Toruńczyk's rank conjecture. The class C C has elementarily fixed-parameter tractable model checking if and only if there is some dNd\in\mathbb{N} such that C C does not transduce Td T_d. 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

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.