Algorithms for Parameterized Constraint Satisfaction Problems

Robert Crowston

Research output: ThesisDoctoral Thesis

485 Downloads (Pure)

Abstract

There are many problems requiring superpolynomial time in the size of the instance. Parameterized complexity considers the problem having an additional parameter, isolating the superpolynomial behaviour. A problem is fixed-parameter tractable if it has an algorithm which has running time polynomial in the size of the instance multiplied by a (usually superpolynomial) function of the parameter.

This thesis considers the parameterized complexity of several problems where the aim is to satisfy a set of constraints. For such problems, it is known that a certain proportion of constraints can be satisfied. We consider the parameterized complexity of such problems with respect to the number of constraints satisfied above this, as well as with respect to other structural parameters.
Original languageEnglish
QualificationPh.D.
Awarding Institution
  • Royal Holloway, University of London
Publication statusUnpublished - 2013

Cite this