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 …

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 …

The Odd Cycle Transversal problem (OCT) asks whether a given undirected graph can be
made bipartite by deleting at most k of its vertices. In a breakthrough result, Reed, Smith, and …

The existence of a polynomial kernel for Odd Cycle Transversal was a notorious open
problem in parameterized complexity. Recently, this was settled by the present authors …

Let G=(V, E) be a graph on n vertices and R be a set of pairs of vertices in V called requests.
A multicut is a subset F of E such that every request xy of R is cut by F, ie every xy-path of G …

In the Edge Clique Cover (ecc) problem, given an undirected graph G and an integer k, we
ask whether one can choose k cliques in G such that each edge of G is contained in at least …

Given a graph G and an integer k, the Feedback Vertex Set (FVS) problem asks if there is a
vertex set T of size at most k that hits all cycles in the graph. The first fixed-parameter …

Data reduction techniques are widely applied to deal with computationally hard problems in
real world applications. It has been a long-standing challenge to formally express the …