# IEEE Symposium on Logic in Computer Science

LICS Home - LICS Awards - LICS Newsletters - LICS Archive - LICS Organization - Logic-Related Conferences - Links

# Logic in Computer Science (LICS 2006)

## Paper: Approximation Schemes for First-Order Definable Optimization Problems (at LICS 2006)

Authors: Anuj Dawar Martin Grohe Stephan Kreutzer Nicole Schweikardt

### Abstract

Let \varphi(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 \varphi(X). Then a natural minimisation problem associated with \varphi(X) is to find, in a given graph G, a vertex set S of minimum size such that G satisfies \varphi(S). Similarly, if X only occurs negatively in \varphi(X), then \varphi(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 C 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 C 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.

### BibTeX

  @InProceedings{DawarGroheKreutzerS-ApproximationScheme,
author = 	 {Anuj Dawar and Martin Grohe and Stephan Kreutzer and Nicole Schweikardt},
title = 	 {Approximation Schemes for First-Order Definable Optimization Problems},
booktitle =  {Proceedings of the Twenty-First Annual IEEE Symposium on Logic in Computer Science (LICS 2006)},
year =	 {2006},
month =	 {August},
pages =      {411--420},
location =   {Seattle, Washington, USA},
publisher =	 {IEEE Computer Society Press}
}