The folklore conjecture on first-order model checking in interpretations of bounded-expansion classes
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.
Sources & referencesView supporting material
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
Sign in to submit a solution.
No solutions have been posted yet.