A Unified Theory of Structural Tractability for Constraint Satisfaction and Spread Cut Decomposition

Abstract

In this paper we introduce a generic form of structural
\ndecomposition for the constraint satisfaction
\nproblem, which we call a guarded decomposition.
\nWe show that many existing decomposition
\nmethods can be characterized in terms of finding
\nguarded decompositions satisfying certain specified
\nadditional conditions.
\nUsing the guarded decomposition framework we
\nare also able to define a new form of decomposition,
\nwhich we call a spread cut. We show that
\ndiscovery of width k spread-cut decompositions is
\ntractable for each k, and that the spread cut decomposition
\nstrongly generalize all existing decompositions
\nexcept hypertrees. Finally we exhibit a family
\nof hypergraphs Hn, for n = 1; 2; 3 : : :, where the
\nwidth of the best hypertree decomposition of each
\nHn is at least 3n, but the width of the best spreadcut
\ndecomposition is at most 2n.