Abstract:
This thesis deals with the design of exact algorithms
for various NP-complete optimization problems on graphs like
Vertex Cover, Independent Set, or Dominating Set.
We encounter such problems in a broad variety of
application ranges, e.g., when modelling so-called
facility location tasks in the area of decision analysis
and network design.
The main focus of this work is on solving algorithms
with provable bounds on the running time. Due to the
seemingly unavoidable inherent high combinatorial complexity of the problems
under consideration, we are forced to deal with exponential running
times; our goal, however, is to keep this exponential part as
low as possible. To this end, we follow a recent approach of
so-called 'fixed-parameter algorithms,' where the running time
of an algorithm solving this problem shall
be measured not only in the size of the input instance, but also
in the size of a so-called 'problem parameter.' In this sense,
whereas classical complexity theory
offers a one-dimensional approach,
parameterized complexity theory is a
two-dimensional study of combinatorial problems.
We investigate
from both, a theoretical, as well as a practical point of view,
various methods in the design of fixed-parameter algorithms: data reduction,
bounded search trees, graph separation, and the concept
of tree-decompositions.
In addition, a software-package is presented, which was developed
in our project and which implements most of our algorithms.
Finally, we report on a first series of empirical studies
underpinning the practical strength and usefulness of our algorithms.