menu +

Masters Thesis

On The Infeasibility of Polynomial Kernelization

My Masters' thesis written under the guidance of Prof. Venkatesh Raman, and this survey is a compressed version. The thesis is a more leisurely survey of lower-bound techniques in the context of kernelization (polynomial kernels in particular), which saw a number of exciting breakthroughs during the time that the thesis was written, and continues to enjoy very active development.

Remark: Methods in showing kernel lower bounds have advanced considerably. Some significant omissions include - but are not limited to - the technique of cross-composition and the framework for demonstrating finer lower bounds. Also, the AND Conjecture, stated as one of the major open problems in the area, has since been resolved. Here's a blog post about the result, and here's a talk by Andrew Drucker on his work in the context of AND compression.

Also, here is a survey that explores both upper and lower bounds in kernelization.

Abstract

In approaching a problem that is deemed to be computationally hard, preprocessing steps are often employed as a first attempt at problem simplification. The notion of problem kernelization is a formal framework in which algorithms that simplify problems (instead of solving them) can be analyzed for efficiency. A kernelization algorithm performs data reduction with provable performance bounds. Many NP-complete problems are known to admit kernelization algorithms. However, there are also NP-complete problems for which we do not expect such algorithms (indeed, under reasonable complexity theoretic assumptions, it is known that such algorithms are not possible). This immediately gives us a finer classification of problems that are only understood as intractable in the classical context, in particular, this is one way to discriminate between NP-complete problems.

In the context of parameterized complexity, it is well known that kernelization corresponds exactly to efficient parameterized computation, or fixed parameter tractability. However, not all problems that belong here are "equally efficient", and a more thorough classification may be obtained by examining the efficiency of the kernelization procedures that are known for these problems. Here, a natural measure of efficiency would correspond to the kernel size. We survey methods for establishing that some problems cannot have polynomial-size kernels, under the assumption that the polynomial heirarchy does not collapse to the third level. These methods involve devising "composition algorithms" which are demonstrated for many problems. We suggest a standardization under which the similarity of the compositional techniques used for different problems becomes evident. We also illustrate a problem which, while unlikely to have a polynomial kernel, has multiple (n, to be precise) polynomial sized kernels.

We conclude with pointers to the many directions for future work that have opened up because of these studies.

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

Gallery

A random sample of figures - made with PGF/TikZ.

Neeldhara Misra | Personal Home Page
q l

Using a composition and a polynomial kernel to obtain a distillation, making the two mutually exclusive.

Neeldhara Misra | Personal Home Page
q l

A schematic of the composition for the Disjoint Factors Problem.

Neeldhara Misra | Personal Home Page
q l

An intermediate step in the composition for Colorful Red Blue Dominating Set.

Neeldhara Misra | Personal Home Page
q l

A schematic describing how polynomial parameter transformations work.

Neeldhara Misra | Personal Home Page
q l

An example of a PPT - Red-Blue Dominating Set to Capaciated Vertex Cover.

Neeldhara Misra | Personal Home Page
q l

The argument for k-Leaf OutBranching is not expected to have a polynomial kernel.

Neeldhara Misra | Personal Home Page
q l

A schematic showing the counting argument associated with the original result about why we do not expect Distillation algorithms for NP-complete problems.