#### Alladi Ramakrishnan Hall

#### (Thesis Defence) Classic and approximate kernels for some structural parameters of some covering problems

#### Diptapriyo Majumdar

##### IMSc

*Parameterized Complexity is an approach to cope with NP-hard problems.*

Kernelization or polynomial time preprocessing is an important tool

in designing parameterized algorithms. The goal of kernelization

is to efficiently preprocess the input to an equivalent instance

whose size is simply a function of the parameter. Approximate

(lossy) kernelization is a recently developed framework that links

polynomial time preprocessing with approximation heuristics.

In this thesis, we consider classical and approximate kernelization

complexity of Vertex Cover, Feedback Vertex Set and Connected Vertex Cover when they are parameterized by `deletion

distance' to several easy classes of graphs. In most of the cases,

these deletion distances are provably smaller than the solution

size. We also provide some hardness results, and refute polynomial

kernelizations under complexity theoretic assumptions for some of

these problems.

We also look at the kernelization complexity of Disjoint Cycle Packing, when some natural relaxations are provided to the

disjointness constraints.

~

~

Done