PhD Thesis

Kernels for the F-Deletion Problem

My PhD thesis written under the joint guidance of Prof. Venkatesh Raman and Prof. Saket Saurabh. The thesis is largely concerned with the Planar F-deletion problem, which seeks the smallest number of vertices that we must delete from a graph G to ensure that it contains no minor models of graphs from F (F is a family of connected graphs containing at least one planar graph). The thesis explores the kernelization complexity and explores some closely related structural questions. En route, we devise an approximation algorithm for the problem which can be useful in other contexts. An interesting variety of techniques are called upon as we journey through variants of the general question, ranging from applications of Courcelle's theorem to using protrusion-based techniques.

Remark: There has been substantial progress in this line of work since the writing of the thesis. In particular, the question of whether Planar F-deletion admits a polynomial kernel is fully resolved and the answer is affirmative. The most recent work makes no assumption about the connectivity of the graphs in $F$. The status of the general F-deletion problem, where we drop the assumption that F contains at least one planar graph, continues to be an intriguing open problem.

Abstract

In this thesis, we use the parameterized framework 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) \in L$ in time $f(k) \cdot 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 our attention in this thesis is the F-Deletion problem, a vastly general question that encompasses many fundamental optimization problems as special cases. In particular, we 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. We also study 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.

(Ideally viewed in full screen - use the button at the bottom-right corner if you are not using a mobile device.)