Nowhere FO dense conjecture for FO model checking
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.
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.