Nowhere FO dense conjecture for FO model checking
Let be a graph class, and for every FO formula let be a graph such that is not an induced subgraph of any member of . Nowhere FO dense conjecture. If has this property, then has an FPT algorithm for FO model checking. This conjecture proposes a logical analogue of nowhere denseness and asks whether the associated forbidden-induced-subgraph condition guarantees fixed-parameter tractability; the source gives no resolution.
References
Primary source
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
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.