| Presented at | : | CP-2009 Conference, Tutorial 1 |
| Presenter | : | Barry O'Sullivan Igor Razgon |
| Date and time | : | Monday, September 21, 2009; 2:00pm |
| Location | : | Rectorate, New University of Lisbon, Portugal |
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 NP-Complete or harder. The field of parameterised complexity provides an orthogonal view to classical complexity theory. It attempts to deal with NP-Hardness by identifying problems whose exponential worst-case 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 fixed-parameter 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 fixed-parameter 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 polynomial-time 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:
- The method of parameterized complexity can be regarded as a theoretical foundation for particular kinds of reformulation and preprocessing in constraint programming.
- Researchers in the area of constraint programming can apply their training and experience in reformulation and preprocessing in order to solve hard open problems in the area of parameterized complexity; this is, in fact, what has happened in our case.
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 in-depth analysis of one challenging open problem that was recently resolved by the tutorialists that is of interest in satisfiability and constraint optimization.
|
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 real-world 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 well-known open problems in the field of parameterised complexity: the classification of both the Directed Feedback Vertex Set Problem and the Min2CNF Deletion (Almost 2-SAT) 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).