A Unifying Theory of Structural Decompostions for the Constraint Satisfaction Problems

Abstract

In this talk (draft paper) we develop the theory of structural decompositions for the CSP.  We begin with the very general notion of a guarded decomposition and make several simplifying assumptions to arrive a the definition of an acyclic guarded cover.
We show how many existing decompositions can seen as acyclic guarded covers.  We develop a generic algorithm for discovering acyclic guarded covers under the further assumption that they have a join tree satisfying a simple extra condition.  We show that many existing decompositions do in fact satisfy this extra condition.
Using this theory we are able to describe a new class of structural decompostion which we call spread cuts.  These generalise many existing decomposition methods.  We present a class of hypergraphs whose spread cut width is significantly smaller than their hypertree width.
The definition of a guarded decomposition and the algorithm for discovering them were motvated by the similar algorithms developed by Gottlob, Scarcello and Leone in their work on hypertrees.  The authors also wish to acknowledge that an acyclic guarded decomposition is very similar to a generalised hypertree decomposition as described in the hypertree literature.