To solve NP-hard problems, polynomial-time preprocessing is a natural and promising
approach. Preprocessing is based on data reduction techniques that take a problem's input …

In a parameterized problem, every instance I comes with a positive integer k. The problem is
said to admit a polynomial kernel if, in polynomial time, one can reduce the size of the …

Given a graph G and an integer k≥ 0, the NP-complete Induced Matching problem asks
whether there exists an edge subset M of size at least k such that M is a matching and no …

We develop a generic framework for deriving linear-size problem kernels for NP-hard
problems on planar graphs. We demonstrate the usefulness of our framework in several …

Parameterized Algorithms and Complexity is a natural way to cope with problems that are
considered intractable according to the classical P versus NP dichotomy. In practice, large …

The fixed-parameter approach is an algorithm design technique for solving combinatorially
hard (mostly NP-hard) problems. For some of these problems, it can lead to algorithms that …

The notion of a “problem kernel” plays a central role in the design of fixed-parameter
algorithms. The FPT literature is rich in kernelization algorithms that exhibit fundamentally …

The domination number of a graph G=(V, E) is the minimum size of a dominating set U⊆ V,
which satisfies that every vertex in V\U is adjacent to at least one vertex in U. The notion of a …

We discuss different variants of linear arrangement problems from a parameterized
perspective. More specifically, we concentrate on developing simple search tree algorithms …

The domination number of a graph G=(V, E) is the minimum size of a dominating set U⊆ V,
which satisfies that every vertex in V∖ U is adjacent to at least one vertex in U. The notion of …