Approximation schemes for first-order definable optimisation problems

Let psi(X) be a first-order formula in the language of graphs that has a free set variable X, and assume that X only occurs positively in psi(X). Then a natural minimisation problem associated with psi(X) is to find, in a given graph G, a vertex set S of minimum size such that G satisfies psi (S). Similarly, if X only occurs negatively in psi(X), then psi(X) defines a maximisation problem. Many well-known optimisation problems are first-order definable in this sense, for example, MINIMUM DOMINATING SET or MAXIMUM INDEPENDENT SET. We prove that for each class W of graphs with excluded minors, in particular for each class of planar graphs, the restriction of a first-order definable optimisation problem to the class L has a polynomial time approximation scheme. A crucial building block of the proof of this approximability result is a version of Gaifman's locality theorem for formulas positive in a set variable. This result may be of independent interest.