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 …

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 …

Treewidth is a graph parameter of fundamental importance to algorithmic and structural
graph theory. This article surveys several graph parameters tied to treewidth, including …

We consider the classical Minimum Balanced Cut problem: given a graph G, compute a
partition of its vertices into two subsets of roughly equal volume, while minimizing the …

Let G=(V, E, w) be a weighted, directed graph subject to a sequence of adversarial edge
deletions. In the decremental single-source reachability problem (SSR), we are given a fixed …

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 …

A graph H is an induced minor of a graph G if H can be obtained from G by vertex deletions
and edge contractions. We show that there is a function f (k, d)= O (k 10+ 2 d 5) so that if a …

Abstract We study the Excluded Grid Theorem, a fundamental structural result in graph
theory, that was proved by Robertson and Seymour in their seminal work on graph minors …

Bidimensionality theory appears to be a powerful framework in the development of meta-
algorithmic techniques. It was introduced by Demaine et al.[J. ACM 2005] as a tool to obtain …

We show that the Maximum Weight Independent Set problem (MWIS) can be solved in quasi-
polynomial time on H-free graphs (graphs excluding a fixed graph H as an induced …