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.
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 language | English |
|---|---|
| Qualification | Ph.D. |
| Awarding Institution |
|
| Publication status | Unpublished - 2013 |