An Isaac Newton Institute Programme

Logic and Algorithms

Fixed-parameter algorithms for propositional satisfiability and constraint satisfaction.

27th March 2006

Author: Stefan Szeider (Durham)

Abstract

The framework of parameterized complexity provides a framework for dealing with NP-hard problems. The idea is to associate with a problem instance a parameter, usually a non-negative integer k, which is small for instances of relevance, and to develop exact algorithms with running times that are possibly exponential in the parameter but uniformly polynomial in the instance size.

The majority of combinatorial problems studied in the framework of parameterized complexity suggest a "natural" parameter. For example, a natural parameter for the VERTEX COVER problem is an upper bound on the size of the vertex cover one searches for. However, problems such as propositional satisfiability and constraint satisfaction do not suggest a single natural parameter; in fact, there are numerous possibilities for parameters that one can consider. The identification of parameters that are as general as possible and which are still accessible to fixed-parameter algorithms is an important research objective.

In the talk we will survey recent results on fixed-parameter algorithms for propositional satisfiability and constraint satisfaction. In particular, we will consider parameters that bound the cyclicity of instances, and parameters that bound the distance of instances from a polynomial-time solvable base class.