FO model checking on FO interpretations of nowhere dense classes
Let be a nowhere dense graph class, and let be a graph class FO interpretable in . FO model-checking conjecture. The class has an FPT algorithm for FO model checking. This conjecture asks whether fixed-parameter tractability of FO model checking extends from nowhere dense classes to all graph classes FO interpretable in them; the source presents it as an explicit conjecture, and no resolution is given.
References
- Jakub Gajarský, Petr Hliněný, Daniel Lokshtanov, Jan Obdržálek and M. S. Ramanujan, “A New Perspective on FO Model Checking of Dense Graph Classes”, arXiv:1805.01823 (2018).
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.