Logik in der Informatik Prof. Dr. Martin Grohe

Institut für Informatik

Decomposition Methods without Decompositions in Constraint Satisfaction

The Constraint Satisfaction Problem (CSP) is a general framework for the modelling of search problems. Due to its general intractability, there has been much research aimed at identifying restrictions of the CSP that guarantee polynomial-time tractability. One line of work -- the topic of this talk -- has focused on so-called structural restrictions, or "decomposition methods", where the interaction among variables is restricted. This line of work has its origins in work of Dechter and Pearl ('89) and Freuder ('90) on bounded treewidth. In this talk, I will survey some of the results in the area, with a focus towards recent work (joint with Victor Dalmau) showing the tractability of generalized hypertreewidth in CSP (paper available on my home page). A feature of this recent work is that the algorithms given do not need or compute any form of tree decomposition, even though the notion of generalized hypertreewidth is defined in terms of tree decompositions.