Abstract:
In this thesis, the parameterized framework is used for the design and analysis
of algorithms for NP-complete problems. This amounts to studying the parameterized
version of the classical decision version. Herein, the classical language
appended with a secondary measure called a “parameter”. The central notion in
parameterized complexity is that of fixed-parameter tractability, which means given
an instance (x, k) of a parameterized language L, deciding whether (x, k) an element of L in
time f(k) ·p(|x|), where f is an arbitrary function of k alone and p is a polynomial
function. The notion of kernelization formalizes preprocessing or data reduction,
and refers to polynomial time algorithms that transform any given input into an
equivalent instance whose size is bounded as a function of the parameter alone.
The center of attention in this thesis is the F-Deletion problem, a vastly
general question that encompasses many fundamental optimization problems as
special cases. In particular, provide evidence supporting a conjecture about the
kernelization complexity of the problem, and this work branches off in a number of
directions, leading to results of independent interest. This thesis also studies the Colorful Motifs problem, a well-known question that arises frequently in practice. Our investigation demonstrates the hardness of the problem even when restricted to
very simple graph classes.