The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

Skip to content



Fixed-parameter algorithms for propositional satisfiability and constraint satisfaction

Szeider, S (Durham)
Monday 27 March 2006, 11:00-12:00

Seminar Room 2, Newton Institute Gatehouse


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.


[pdf ]

Back to top ∧