A Probabilistic Approach to Problems Parameterized Above or Below Tight Bounds

Gregory Gutin, Eun Jung Kim, Stefan Szeider and Anders Yeo

J. Comput. Syst. Sci., vol. 77, no. 2, pp. 422-429, 2011.

A preliminary version appeared in the Proceedings of IWPEC 2009, 4th International Workshop on Parameterized and Exact Computation, LNCS 5971, Springer, 2009.

Abstract:

We introduce a new approach for establishing fixed-parameter tractability of problems parameterized above tight lower bounds or below tight upper bounds. To illustrate the approach we consider two problems of this type of unknown complexity that were introduced by Mahajan, Raman and Sikdar (J. Comput. Syst. Sci. 75, 2009). We show that a generalization of one of the problems and three nontrivial special cases of the other problem admit kernels of quadratic size. As a byproduct we obtain a new probabilistic inequality that could be of independent interest. Our new inequality is dual to the Hypercontractive Inequality.

Keywords: parameterized problems; above tight bounds; fixed-parameter tractable; kernel; Hypercontractive Inequality; probabilistic method.

Download: [paper pdf]