Backtracking Procedures for Hypertree, HyperSpread and Connected Hypertree Decomposition of CSPs
Abstract
Hypertree decomposition has been shown to be the most general CSP decomposition method. However, so far the exact methods are not able to find optimal hypertree decompositions of realistic instances. We present a backtracking procedure which, along with isomorphic component detection, results in optimal hypertree decompositions. We also make the procedure generic; variations of which results in two new tractable decompositions: hyperspread and connected hypertree. We show that the hyperspread width is bounded by both the hypertree width and the spread cut width, which solves a recently stated open problem. In our experiments on several realistic instances, our methods find many optimal decompositions, while the previous methods can find at most one.
Cite
Text
Subbarayan and Andersen. "Backtracking Procedures for Hypertree, HyperSpread and Connected Hypertree Decomposition of CSPs." International Joint Conference on Artificial Intelligence, 2007.Markdown
[Subbarayan and Andersen. "Backtracking Procedures for Hypertree, HyperSpread and Connected Hypertree Decomposition of CSPs." International Joint Conference on Artificial Intelligence, 2007.](https://mlanthology.org/ijcai/2007/subbarayan2007ijcai-backtracking/)BibTeX
@inproceedings{subbarayan2007ijcai-backtracking,
title = {{Backtracking Procedures for Hypertree, HyperSpread and Connected Hypertree Decomposition of CSPs}},
author = {Subbarayan, Sathiamoorthy and Andersen, Henrik Reif},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2007},
pages = {180-185},
url = {https://mlanthology.org/ijcai/2007/subbarayan2007ijcai-backtracking/}
}