Nowhere FO dense conjecture for FO model checking

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.

Sources & referencesView supporting material

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.