Fundamentals of Parameterized Complexity

We give basic results and definitions in classical complexity theory. These include

NP

- and

PSpace

-completeness, concrete Karp and Cook reductions, the Cook–Levin Theorem, and the Stockmeyer–Meyer Theorem. We introduce some ideas, such as advice classes and randomized reductions, that will be of use later in the book.

The fundamental notions of parameterized complexity are introduced.

The fundamental method of bounded search trees is introduced. This is essential for all investigations in parameterized complexity.

Kernelization is a pre-processing technique, which takes a large problem and shrinks it to a smaller one that has size depending only on the parameter. This method is another

fundamental

technique in parameterized complexity and we introduce it in this chapter.

We look at further kernelization techniques and in particular Turing kernels and kernelizations based upon Crown Structures.

We introduce the technique of iterative compression. We illustrate how this can be combined with analytical techniques such as measure and conquer.

We explore a number of elementary techniques including the extremal method, greedy localization and bounded variable integer programming.

We introduce the important technique of color coding. We also show how this relates to randomized divide and conquer. Finally, we will show how to tighten the running times for randomized algorithms with Koutis’ (Proceedings of 35th International Colloquium on Automata, Languages and Programming, Part I, pp. 575–586,

2008

) idea of using

algebraic

general methods of speeding up algorithms obtained by color coding.

We begin to analyze the relationship between classical optimization problems and parameterized complexity. We explore syntactically defined classes of optimization problems that capture some of the main issues.

A central concept in modern algorithm design uses the metaphor of treewidth, both in its original form for graphs, and its extensions to other areas. This chapter is devoted to developing the basic theory of treewidth, and fundamental aspects of producing treewidth algorithms by running dynamic programming on graphs.

We look at heuristics for computing optimal or near-optimal tree decompositions.

This chapter explores the basics of finite-state automata theory, including the generalization of the main theorems of linear automata theory to tree automata, and how these tools lead to FPT algorithmic methods, meta-theorems, and important concrete applications.

We examine monadic second-order logic MS

2

for graphs. We give a “Myhill–Nerode” proof of Courcelle’s Theorem: that MS

2

model checking, parameterized by the treewidth of the input graph, and the size of the MS

2

formula, is linear time fixed-parameter tractable. Seese’s Theorem, and MS

1

logic are also surveyed.

Applications of the ideas of width metrics, and associated FPT algorithmic strategies, are discussed in the context of logic and databases, matroids, knot polynomials, and other settings. The notion of local treewidth is introduced and the analogue of Courcelle’s Theorem for first order formulas and local treewidth is proved.

In this chapter, we explore two methods for proving fixed-parameter tractability results based on the basic graph-theoretic algorithmic technique of depth-first search. These methods also build upon and extend the bounded-treewidth ideas of Chap.

12

.

Treewidth is the best studied and perhaps the most important of a large number of width metrics in graphs. In this chapter we will explore some other metrics which have proven useful.

As we will see, well-quasi-orderings (

WQO

s) provide a powerful engine for demonstrating that classes of problems are

FPT

. In the next section, we will look at the rudiments of the theory of

WQO

s, and in subsequent sections, we will examine applications to combinatorial problems.

We give a broad sketch of the ideas of the Graph Minor Theorem. We discuss excluding a forest and more general consequences of excluding a graph as a minor. We prove the Thomas Lemma on the existence of lean and linked decompositions. We discuss the related immersion and topological orderings.

We introduce methods to apply the Graph Minor Theorem and demonstrate theoretical tractability.

We introduce the basic premises of parameterized reductions. They are fundamental to all hardness theory in this area, and essential for all of the rest of the book.

We introduce the basic class

W

[1] and prove the fundamental analogue of the Cook–Levin Theorem. This is central to much of the hardness theory for parameterized complexity.

In this chapter we will analyze a couple of further

W

[1]-hardness and completeness results. These examples are taken from logic and formal language theory. We also look at further applications of the theory to arenas such as algebra and number theory in the exercises where problems such as the following are proven to be

W

[1]-hard.

We introduce the

W

-hierarchy of parameterized complexity classes in the tower

$$\mathrm{FPT}=W[0] \subseteq W[1] \subseteq W[2] \subseteq\cdots \subseteq W[t]\subseteq \cdots\subseteq W[\mathrm{SAT}]\subseteq \cdots\subseteq W[\mathrm{P}]. $$

Presumably, all the inclusions are proper. The

W

-Hierarchy gives us means of comparing parameterized problems that are presumably

not

in

FPT

, with respect to the “strength” of their parameterized intractability. The key idea is to use a form of

circuit depth

in defining the classes. We discuss the remarkable fact that “almost all” (or at least a very large percentage) of the natural parameterized problems investigated to date are precisely

complete

for one of the first three classes in this hierarchy, a remarkable empirical finding that supports the definitional framework. We also introduce a natural generalization called the

W

∗

[

t

]-hierarchy, about which only a little (but for exact parameterized complexity analysis, a

useful little

), is so far known.

In this chapter, we will give proofs of the two structural collapses noted in Chap. 23.2.1 after Theorem 23.3.1. The techniques are similar to the proof of the Normalization Theorem.

We introduce the classes

W

[P] and variations, proving a number of concrete hardness and membership results for this level of the

W

-hierarchy.

We define parameterized complexity classes that allow us to investigate the complexity of

k

-move games. We establish a number of concrete hardness and completeness results for games such as the

k

-move versions of

Geography

and

Chess

. We relate these classes to bounded space computations.

We look at the X-classes, and give analogues of exponential time, namely the class XP. We report on how

FPT

is provably (unconditionally) a

proper

subset of XP. We also prove an XP-completeness result.

We give a uniform circuit basis for the

W

-hierarchy. We introduce the syntactic classes

G

[

t

] and prove the Replacement and Tradeoff Theorems. These lead to evidence that the

W

-hierarchy is proper and give a different perspective on its naturality.

We relate

NP

to parameterized complexity via the ETH, SETH, and prove results on

XP

-optimality. Namely, we give methods to show that, under reasonable hypotheses, current algorithms for various computational tasks are

optimal

up to an

O

-factor.

We introduce powerful new techniques to show that FPT parameterized problems

do not

have polynomial-sized many : 1 kernels, under standard assumptions of classical complexity theory. A new completeness program for exploring the issue for Turing kernelization is also described.

This chapter introduces the idea of parameterized approximation. This is a method that either gives a “no” guarantee or an approximate solution. That is, we either see a certificate that there is no solution of size

k

or we find an approximate solution of size

g

(

k

). This chapter provides applications of parameterized approximation, as well as methods of demonstrating complete inapproximability, meaning that there is

no

approximate solution for any computable function

g

(

k

).

In this chapter, we will first look at parameterized counting problems as an analog to the classical problem of counting. We establish the classes #

W

[

t

] and related issues, and prove completeness results. We present the Flum–Grohe results on the hardness of counting

k

-cycles. Later we introduce a formal model for parameterized randomization. We prove an analog of the Valiant–Vazirani Theorem.

In this final chapter, we describe what we think are some of the most important open problems of the field. In the first book, Downey and Fellows (Parameterized Complexity. Monographs in Computer Science, Springer, Berlin,

1999

), we offered two lists of problems, 18 altogether, that we then thought significant and especially challenging. As this book goes to press, 12 of these have been resolved! Many of the solutions to these problems involved significant new ideas and advances in the field.

In this appendix, we develop some basic machinery which allows us to begin work in

topological graph theory

, an area where the emphasis is on connectivity and “shape”.

In this appendix, we supply a basic introduction to important min/max theorems concerning graph separators.