Catálogo de publicaciones - libros

Tree width is a parameter that measures the similarity of a graph or relational structure with a tree. We will see in this chapter that many NP-hard decision and optimization problems are fixed-parameter tractable when parameterized by the tree width of the input structure. A very powerful and general theorem due to Courcelle states that this is the case for all problems that are definable in monadic second-order logic.

In the previous chapter, we saw that many graph problems that are hard in general become tractable when restricted to input graphs of bounded tree width. We have also seen examples of hard problems that become tractable on graphs of bounded degree (the parameterized dominating set problem is an example, see Corollary 1.20).

The homomorphism problem for relational structures is a fundamental algorithmic problem playing an important role in different areas of computer science. For example, constraint satisfaction problems in artificial intelligence and the containment problem for conjunctive queries in database theory can be viewed as homomorphism problems. We briefly covered the homomorphism problem in Chap. 7, where we proved that its parameterization by the size of the left-hand side structure is Wi-complete. In the first two sections of this chapter we study restrictions of the homomorphism problem obtained by requiring the left-hand side structure to be from a certain class of structures. We give a complete classification of the complexity of such restrictions, both in the sense of polynomial time solvability and fixed-parameter tractability. Once again, tree width plays a central role. As a by-product, we obtain a new characterization of the question FPT W entirely in terms of classical complexity. In the third section we study the related embedding problem. We introduce a powerful new technique for the design of fpt-algorithms, which is known as color coding. In its basic form, color coding yields randomized fpt-algorithms. These can be derandomized by sophisticated hashing techniques. We apply these techniques to prove that the embedding problem, restricted to left-hand side structures of bounded tree width, is fixed-parameter tractable.

Some of the deepest and most fascinating results of (classical) complexity theory are concerned with counting problems. A parameterized complexity theory of counting problems has only been developed fairly recently and is still in its early stages. This chapter is an introduction into the state of the art of this theory.

In the definition of fixed-parameter tractability we allowed arbitrary computable functions to bound the dependence on the parameter of the running time of an fpt-algorithm. This liberal definition was mainly justified by the hope that "natural" problems in FPT will have "low" parameter dependence. While this is true for many problems, in Theorem 10.18 we saw that there is no elementary function bounding the parameter dependence of -MC(TREE,FO), the parameterized model-checking of first-order logic on the class of trees. There are viable alternatives to the notion of fixed-parameter tractability obtained by simply putting upper bounds on the growth of the parameter dependence . Natural choices are and .

This last chapter of the book is concerned with subexponential fixed-parameter tractability, that is, with the class . Subexponential fixed-parameter tractability is intimately linked with the theory of exact (exponential) algorithms for hard problems, which is concerned with algorithms for NP-hard problems that are better than the trivial exhaustive search algorithms, though still exponential. For example, there has been a long sequence of papers on exact algorithms for the 3-satisfiability problem; the currently best (randomized) algorithm for this problem has a running time of time for instances with n variables. There are numerous further examples of very nice nontrivial algorithms for hard problems, but a systematic complexity theory is still in its infancy. A question that has turned out to be central for such a theory is whether the 3-satisfiability problem can be solved in time .