Preprocessing, or data reduction, is a standard technique for simplifying and speeding up
computation. Written by a team of experts in the field, this book introduces a rapidly …

The goal of this textbook is twofold. First, the book serves as an introduction to the field of
parameterized algorithms and complexity accessible to graduate students and advanced …

Kernelization is a formalization of efficient preprocessing, aimed mainly at combinatorially
hard problems. Empirically, preprocessing is highly successful in practice, eg, in state-of-the …

We introduce the framework of cross-composition for proving kernelization lower bounds. A
classical problem L\and/or-cross-composes into a parameterized problem Q if it is possible …

Parameterization and approximation are two popular ways of co** with NP-hard
problems. More recently, the two have also been combined to derive many interesting …

In this paper we propose a new framework for analyzing the performance of preprocessing
algorithms. Our framework builds on the notion of kernelization from parameterized …

In the PLANAR DISJOINT PATHS problem, one is given an undirected planar graph with a
set of k vertex pairs \left(s_i,t_i\right) and the task is to find k pairwise vertex-disjoint paths …

We prove that Multicut in directed graphs, parameterized by the size of the cutset, is W [1]-
hard and hence unlikely to be fixed-parameter tractable even if restricted to instances with …

The maximum stable set problem is NP-hard, even when restricted to triangle-free graphs. In
particular, one cannot expect a polynomial time algorithm deciding if a bull-free graph has a …

This paper deals with the FEEDBACK VERTEX SET problem on undirected graphs, which
asks for the existence of a vertex set of bounded size that intersects all cycles. Due it is …