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 …

Parameterized complexity/multivariate complexity algorithmics is an exciting field of modern
algorithm design and analysis, with a broad range of theoretical and practical aspects that …

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 …

Classical complexity theory analyzes and classifies problems by the amount of a resource,
usually time or space, that is required by algorithms solving them. It was a fundamental idea …

This research-level text is an application-oriented introduction to the growing and highly
topical area of the development and analysis of efficient fixed-parameter algorithms for …

For many fixed-parameter problems that are trivially soluable in polynomial time, such as (k-)
DOMINATING SET, essentially no better algorithm is presently known than the one which …

Kernelization is a strong and widely-applied technique in parameterized complexity. A
kernelization algorithm, or simply a kernel, is a polynomial-time transformation that …

Leaf-labelled trees are widely used to describe evolutionary relationships, particularly in
biology. In this setting, extant species label the leaves of the tree, while the internal vertices …

The OR-SAT problem asks, given Boolean formulae Φ1,..., Φm each of size at most n,
whether at least one of the Φi's is satisfiable. We show that there is no reduction from OR …

In this paper, we show that the problems Disjoint Cycles and Disjoint Paths do not have
polynomial kernels, unless NP⊆ coNP/poly. Thus, these problems do not allow polynomial …