A unified theory of structural tractability for constraint satisfaction problems
David Cohen, Peter Jeavons and Marc Gyssens 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 Hn, for n=1,2,3..., where the minimum width of any hypertree decomposition of each Hn is 3n, but the width of the best spread-cut decomposition is only 2n+1.
infojournal | Journal of Computer and System Sciences |
note | Earlier, uncorrected, version appears in Proceedings of IJCAI'05, pp. 72—77: http://www.ijcai.org/papers/0521.pdf |
pages | 721-743 |
volume | 74 |
year | 2008 |
links
BibTeX
Link (pdf)
DOI (10.1016/j.jcss.2007.08.001)
related pages
|
