zbMATH — the first resource for mathematics

Parametrized complexity: A framework for systematically confronting computational intractability. (English) Zbl 0935.68046
Graham, Ronald L. (ed.) et al., Contemporary trends in discrete mathematics. From DIMACS and DIMATIA to the future. Proceedings of the DIMATIA-DIMACS conference, Štiřín Castle, Czech Republic, May 19-25, 1997. Providence, RI: American Mathematical Society. DIMACS, Ser. Discrete Math. Theor. Comput. Sci. 49, 49-99 (1999).
Summary: We give an overview of parameterized computational complexity in the broad context of the problem of coping with computational intractability. We give some examples of how fixed-parameter tractability techniques can deliver practical algorithms in several different ways, including: (1) by providing useful exact algorithms for small parameter ranges, and (2) by providing guidance in the design of heuristic algorithms. In particular, we describe an improved FPT algorithm for vertex cover, a practical FPT algorithm for the Maximum Agreement SubTree (MAST) problem parameterized by the number of species to be deleted, and new heuristics for these problems based on FPT techniques. In the course of making this overview, we also investigate some structural and hardness issues. We prove that an important parameterized problem in artificial intelligence, strips planning (where the parameter is the size of the plan) is complete for \(W[1]\). As a corollary, this implies that \(k\)-step reachability for Petri nets is also complete for \(W[1]\). We describe how the concept of treewidth can be applied to strips planning and other problems of logic to obtain FPT results. We describe a surprising structural result concerning the top end of the parameterized complexity hierarchy: the naturally parameterized graph \(k\)-coloring problem cannot be resolved with respect to XP either by showing membership in XP, or by showing hardness for XP without settling the \(\text{P}= \text{NP}\) question one way or the other.
For the entire collection see [Zbl 0919.00042].

68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q25 Analysis of algorithms and problem complexity
68Q45 Formal languages and automata
03D15 Complexity of computation (including implicit computational complexity)
03A05 Philosophical and critical aspects of logic and foundations