"On the Decomposition of Constraint Satisfaction Problems"
Dr. Phillipe Jégou
WHEN: Friday, October 30. 2009 at 1 PM
WHERE: Room 4421, Graduate Center
Abstract
This talk deals with decomposition methods for solving Constraint Satisfaction Problems (CSPs). The classical approaches are based on the notion of tree-decomposition of graphs (or hypertree-decomposition of hypergraphs) whose theoretical time complexity is bounded by O(exp(w+1)) where w is called the tree-width of the constraint network. For sparse networks, these methods can significantly improve the classical bound which is O(exp(n)) where n is the number of variables in the CSP. Unfortunately, for dense networks (w is not far from n, e.g. complete graphs where w+1 = n), these approaches are without interest. Here we present an approach that has been defined to manage this kind of network. It is based on the analysis of the "micro-structure" of a CSP. The micro-structure of a CSP is the graph defined by the compatible relations between variable-value pairs: vertices form these pairs, and edges are defined by pairs of compatible vertices. Given the micro-structure of a CSP, preprocessing can simplify the problem with a decomposition of the domains of the variables. The method is based on the theory of triangulated graphs. We also present an extension of this approach based on a generalization of triangulated graphs, called CSGk graphs. Some experimental results will be presented during the talk, along with recent results on an extension of this work that allows us to define new tractable classes of CSP. Finally, the connection with the satisfiabilty problem (SAT) will be presented.
Philippe Jégou is a professor of computer science at the University Paul Cézanne of Marseille (France). He received his PhD in computer science from University of Montpellier (France) in 1991. He headed the INCA Team (INference, Constraints and Applications) at the Laboratory LSIS-CNRS of Marseille from 2000 to 2008. He is Director of the Department of Mathematics, Computer Sciences and Systems at University Paul Cézanne of Marseilles. His research interests include constraint satisfaction and algorithms for artificial intelligence. Recent references to publications can be found at http://www.lsis.org/~philippe_jegou.annee_categorie.html