A unified theory of structural tractability for constraint satisfaction problems

Journal article

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 andEta;n, for n = 1, 2, 3 ..., where the minimum width of any hypertree decomposition of each andEta;n is 3n, but the width of the best spread-cut decomposition is only 2 n + 1.

Authors: Cohen, D; Jeavons, P; Gyssens, M

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Elsevier
• Journal: Journal of Computer and System Sciences
• Volume: 74
• Issue: 5
• Pages: 721-743
• Publication date: 2008-08-01
• DOI: 10.1016/j.jcss.2007.08.001
• EISSN: 1090-2724
• ISSN: 0022-0000
• Language: English
• Keywords: complexity; hypertree; constraints; structural decomposition