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

About 9 years old · traced to

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.

References

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.