The folklore conjecture on first-order model checking in interpretations of bounded-expansion classes
Let be a graph class with bounded expansion, let be a simple first-order graph interpretation scheme, and let be a first-order property to be tested. The interpretation consists of the graphs obtained by applying to graphs in . Folklore conjecture. First-order model checking is fixed-parameter tractable on , parameterized by , the interpretation scheme , and the first-order property to be tested. This conjecture concerns the tractability of first-order model checking for graph classes that may be dense but are structurally derived from sparse classes. It remains open in the stated generality.
References
Primary source
Jakub Gajarsky and Daniel Kral, “Recovering sparse graphs”, arXiv:1709.09985 (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.