Catálogo de publicaciones - libros

In this chapter, we introduce parameterized problems and the notion of fixed-parameter tractability. We start with an informal discussion that highlights the main issues behind the definition of fixed-parameter tractability. In Sect. 1.2, we begin the formal treatment. In Sect. 1.3, we consider a larger example that introduces some of the most fundamental parameterized problems and the most basic technique for establishing fixed-parameter tractability, the method of bounded search trees. In Sect. 1.4 and Sect. 1.5 we exemplify how the parameterized approach may help to gain a better understanding of the complexity of fundamental algorithmic problems by considering applications in two different areas, approximation algorithms and automated verification. Finally, in Sect. 1.6, we give several equivalent characterizations of fixed-parameter tractability.

In this chapter, we start our development of the theory of . In general, no parameterized complexity theory is needed to find an fpt-algorithm for a concrete fixed-parameter tractable problem. The main purpose of the theory is to give evidence that certain problems are fixed-parameter tractable (just as the main purpose of the theory of NP completeness is to give evidence that certain problems are not polynomial time computable). In the classical theory, the notion of NP-completeness is central to a nice, simple, and far-reaching theory for intractable problems. Unfortunately, the world of parameterized intractability is more complex: There is a big variety of seemingly different classes of intractable parameterized problems.

In the previous section, we made a first attempt to define a parameterized analogue of the class NP, without much success. In this section we will take up this question again. We shall see in the course of this book that there is no definite single class that can be viewed as "the parameterized NP." Rather, there is a whole hierarchy of classes playing this role. The classW[P] studied in this section can be placed on top of this hierarchy. It is one of the most important parameterized complexity classes.

The most important classical time and space complexity classes, such as PTIME, NP, or PSPACE, have clean definitions in terms of resource-bounded Turing machines. It is well-known (though still surprising) that most natural decision problems are complete for one of these classes; the consequence is a clear and simple complexity theoretic classification of these problems. However, if more refined complexity issues such as approximability, limited nondeterminism, or parameterizations are taken into account, the landscape of complexity classes becomes much more unwieldy. This means that the natural problems tend to fall into a large number of apparently different classes. Furthermore, these classes usually do not have clean machine characterizations, but can only be identified through their complete problems.

In this chapter, we introduce two hierarchies of parameterized complexity classes that play a central role in the theory of parameterized intractability: the W- and the A-. The two hierarchies will be studied in detail in the following chapters. The definitions of the two hierarchies are based on two types of logically defined decision problems we have introduced in the previous chapter: Fagin-defined problems and model-checking problems.

Recall that the W-hierarchy, defined in terms of Fagin definability, may be viewed as a refinement of NP in the world of parameterized complexity theory, whereas the A-hierarchy, defined in terms of model-checking problems, may be viewed as a parameterized analogue of the polynomial hierarchy. Nevertheless, in this section we shall prove that the first levels of both hierarchies coincide, that is, W[1] = A[1].

Based on the syntactic approach to complexity theory laid out in Chap. 4, we introduced the classes W, W, of the W-hierarchy by means of parameterized weighted Fagin-definable problems, more precisely, by the equality We extensively studied in the previous chapter; as we shall see here, many results generalize in one or another form to the whole W-hierarchy. A notable exception is the equali ty we can only show that . We determine fragments of the class of all propositional formulas (in Sect. 7.1) and fragments of first-order logic (in Sect. 7.4) such that the corresp onding parameterized weighted satisfiability problem and the corresponding parameterized model-checking problem, respectively, are -complete. The proofs of fpt-equivalence between parameterized weighted Fagin-definable problems, parameterized weighted satisfiability problems, and para meterized model-checking problems yield various normal forms and ~collapse~ results. Moreover, we prove that, among other problems, the parameterized dominating set problem and the short haltin g problem for nondeterministic multitape Turing machines are -complete.

The classes of A-hierarchy are defined by Since the unparameterized model-checking problem MC() is complete for the th level of the polynomial hierarchy, the A-hierarchy can be viewed as a parameterized analogue of the polynomial hierarchy. In fact, in Sect. 8.1 we shall see that, as the polynomial hierarchy, the A-hierarchy can be characterized by alternating machines. Section 8.2 is technical; in it we prove certain normal form results. In Sect. 8.3, we introduce alternating weighted satisfiability problems and characterize the classes of the A-hierarchy by them. Few natural complete problems are known for classes of the A-hierarchy beyond A[1]. In Sect. 8.4, we give an example of an A[2]-complete problem. We also introduce the class co-A[1] of all parameterized problems whose complement is in A[1] and prove a (maybe surprising) completeness result for this class. In Sect. 8.5, we characterize the A-hierarchy in terms of Fagin definability. In the last three sections of this chapter we discuss a variety of parameterized complexity classes and hierarchies of classes that are related to the A-hierarchy, and, in particular in the last section, to the w-hierarchy.

One of the characterizations of fixed-parameter tractability we obtained in Sect. 1.6 is that a parameterized problem is fixed-parameter tractable if and only if it has a kernelization, that is, a polynomial time many-one reduction that maps a given instance to an instance of size effectively bounded in terms of the parameter. Kernelization may be viewed as preprocessing with an explicit performance guarantee. In this chapter, we will see that kernelization offers a very useful paradigm for designing fpt-algorithms.

Algorithms based on finite automata are very successfully applied in different areas of computer science, for example, automated verification and database systems. Often, such algorithms are fixed-parameter tractable rather than polynomial time. Automata-theoretic algorithms typically apply to logicbased problems such as model-checking problems or database query evaluation. In the following chapters, however, we will see that these techniques can also be used for many combinatorial problems on trees and treelike graphs. Ironically, the automata-theoretic method not only gives us a very general and practically important paradigm for the design of fpt-algorithms, but also generates our first (and the only known) examples of natural fixedparameter tractable problems with superexponential lower bounds on the parameter dependence of fpt-algorithms solving them. More precisely, we prove that (under natural complexity theoretic assumptions) the model-checking problem for first-order and monadic second-order logic on trees is fixedparameter tractable, but not decidable by an fpt-algorithm whose running time is bounded by .