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.
~
~