Approximation Schemes for First-Order Definable Optimisation Problems
Anuj Dawar, Martin Grohe, Stephan Kreutzer, Nicole Schweikardt · 2006
Let phi(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 phi(X). Then a natural minimisation problem associated with phi(X) is to find, in a given graph G, a vertex set S of minimum size such that G satisfies phi(S). Similarly, if X only occurs negatively in phi(X), then phi(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 Gscr 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 Gscr 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