The folklore conjecture on first-order model checking in interpretations of bounded-expansion classes

Let G\mathcal{G} be a graph class with bounded expansion, let II be a simple first-order graph interpretation scheme, and let φ\varphi be a first-order property to be tested. The interpretation I(G)I(\mathcal{G}) consists of the graphs obtained by applying II to graphs in G\mathcal{G}. Folklore conjecture. First-order model checking is fixed-parameter tractable on I(G)I(\mathcal{G}), parameterized by G\mathcal{G}, the interpretation scheme II, and the first-order property φ\varphi 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

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.