CP2009 Tutorial
Exploiting FixedParameter Tractability

General Information
Tutorial Materials) Tutorial slides: available in pdf format (updated 18/09/2009). AcknowledgementsThis tutorial has received support from Science Foundation Ireland (Grant Number 05/IN/I886). 
Overview Many problems we attempt to solve using satisfiability or constraint programming techniques are NPComplete or harder. The field of parameterised complexity provides an orthogonal view to classical complexity theory. It attempts to deal with NPHardness by identifying problems whose exponential worstcase behaviour is, in fact, only polynomially dependent on the size of the problem $n$, but exponentially dependent on a parameter $k$, independent of $n$. Ideally we wish to identify fixedparameter algorithms for solving such problems that rely on parameters that tend to be small in practice. The field of parameterised complexity has many similarities with the areas of satisfiability and constraint solving from both the conceptual point of view as well as through its results. Informally, from the conceptual point of view, there are two broad classes of techniques for the design of fixedparameter algorithms: reformulation and preprocessing. In this context, reformulation means that the search space is represented in such a way that the number of explored possibilities depends exponentially only on the parameter k but polynomially on the input size n. The methodology of preprocessing aims at designing polynomialtime algorithms for reducing the size of the search space. The methodologies of reformulation and preprocessing in parameterized complexity are very similar to what we understand as reformulation and preprocessing in constraint programming. This similarity opens possibilities for two very intriguing interconnections:
In this tutorial we will: provide an overview of the field; survey the work that has been done in the area of parameterised complexity for satisfiability and constraint solving; and present an indepth analysis of one challenging open problem that was recently resolved by the tutorialists that is of interest in satisfiability and constraint optimization.  

Speakers Barry O'Sullivan is Associate Director of the Cork Constraint Computation Centre, Science Foundation Ireland Principal Investigator, President of the Association for Constraint Programming, Chairman of the Artificial Intelligence Association of Ireland, Coordinator of the European Research Consortium for Informatics and Mathematics (ERCIM) Working Group on Constraints, and a member of the Executive Council of the Management Science Society of Ireland. His research interests include realworld applications of artificial intelligence, constraint programming and optimisation technologies. Igor Razgon is a postdoctoral research fellow at the Cork Constraint Computation Centre. As part of their work, the tutorialists have resolved two of the most wellknown open problems in the field of parameterised complexity: the classification of both the Directed Feedback Vertex Set Problem and the Min2CNF Deletion (Almost 2SAT) Problem. Their work on this topic has appeared in the Journal of the ACM, the Journal of Computer and System Sciences, the ACM Symposium on Theory of Computation (STOC), the International Symposium on Automata, Languages and Programming (ICALP), and the Principles and Practice of Constraint Programming (CP). 