A Unified Theory of Structural Tractability for Constraint Satisfaction and Spread Cut Decomposition
Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence. Pages 72-76.
Abstract
In this paper we introduce 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 characterized 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 discovery of width k spread-cut decompositions is tractable for each k, and that the spread cut decomposition strongly generalize all existing decompositions except hypertrees. Finally we exhibit a family of hypergraphs Hn, for n = 1, 2, 3 . . ., where the width of the best hypertree decomposition of each Hn is at least 3n, but the width of the best spreadcut decomposition is at most 2n.
@inproceedings{ijcai2005p34,
title = {A Unified Theory of Structural Tractability for Constraint Satisfaction and Spread Cut Decomposition},
author = {Cohen, David A. and Jeavons, Peter and Gyssens, Marc},
booktitle = {Proceedings of the Nineteenth International Joint Conference on
Artificial Intelligence, {IJCAI-05}},
publisher = {International Joint Conferences on Artificial Intelligence},
pages = {72--76},
year = {2005},
url = {https://ijcai.org/proceedings/2005/34},
}
TY - CPAPER TI - A Unified Theory of Structural Tractability for Constraint Satisfaction and Spread Cut Decomposition AU - Cohen, David A. AU - Jeavons, Peter AU - Gyssens, Marc T2 - Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, IJCAI-05 PB - International Joint Conferences on Artificial Intelligence PY - 2005 SP - 72 EP - 76 UR - https://ijcai.org/proceedings/2005/34 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
