Nowhere FO dense conjecture for FO model checking

About 8 years old · traced to

Let D\mathcal{D} be a graph class, and for every FO formula ψ(x,y)\psi(x,y) let FψF_\psi be a graph such that FψF_\psi is not an induced subgraph of any member of Iψ(D)I_\psi(\mathcal{D}). Nowhere FO dense conjecture. If D\mathcal{D} has this property, then D\mathcal{D} 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

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.