TY  - BOOK
AU  - Neeldhara Misra
TI  - Kernels for the F-Deletion Problem
PY  - 2012///
KW  - Computer Science
KW  - F-Deletion Problem
KW  - Kernelization
KW  - Parameterized Complexity
KW  - Tree Decompositions
KW  - Tree Width
N1  - 2012
N2  - 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
UR  - http://www.imsc.res.in/xmlui/handle/123456789/328
ER  -