A unified theory of structural tractability for constraint satisfaction problems

Abstract

In this paper we derive a generic form of structural decomposition for the constraint satisfaction problem, which we call a guarded decomposition. We show that many existing decomposition methods can be characterised in terms of finding guarded decompositions satisfying certain specified additional conditions. Using the guarded decomposition framework we are also able to define a new form of decomposition, which we call a spread-cut. We show that the discovery of width-k spread-cut decompositions is tractable for each k, and that spread-cut decompositions strongly generalise many existing decomposition methods. Finally we exhibit a family of hypergraphs H-n, for n = 1, 2, 3..., where the minimum width of any hypertree decomposition of each H-n is 3n, but the width of the best spread-cut decomposition is only 2n+1. (c) 2007 Elsevier Inc. All rights reserved.