Deciding first-order properties for sparse graphs
For a fixed graph H, testing whether there exists a homomorphism to H is typically NP-complete. On the other hand, testing whether there exists a homomorphism from H is trivially solvable in polynomial time. However, the exponent of the polynomial depends on H, and since the problem is W[1]-hard, it is unlikely that the dependence could be eliminated. However, by the result of Eppstein, the problem becomes FPT for planar graphs. We present a generalization of this result in two directions: instead of the homomorphism problem, we consider first-order properties, and instead of planar graphs, we allow an arbitrary class with (locally) bounded expansion. This strengthens all previous resuls on testing first-order properties on classes of sparse graphs. The results are based on the joint work with D. Kr´al’ and R. Thomas.