Fast and Parallel Decomposition of Constraint Satisfaction Problems
Abstract
Constraint Satisfaction Problems (CSP) are notoriously hard. Consequently, powerful decomposition methods have been developed to overcome this complexity. However, this poses the challenge of actually computing such a decomposition for a given CSP instance, and previous algorithms have shown their limitations in doing so. In this paper, we present a number of key algorithmic improvements and parallelisation techniques to compute so-called Generalized Hypertree Decompositions (GHDs) faster. We thus advance the ability to compute optimal (i.e., minimal-width) GHDs for a significantly wider range of CSP instances on modern machines. This lays the foundation for more systems and applications in evaluating CSPs and related problems (such as Conjunctive Query answering) based on their structural properties.
Cite
Text
Gottlob et al. "Fast and Parallel Decomposition of Constraint Satisfaction Problems." International Joint Conference on Artificial Intelligence, 2020. doi:10.24963/IJCAI.2020/161Markdown
[Gottlob et al. "Fast and Parallel Decomposition of Constraint Satisfaction Problems." International Joint Conference on Artificial Intelligence, 2020.](https://mlanthology.org/ijcai/2020/gottlob2020ijcai-fast/) doi:10.24963/IJCAI.2020/161BibTeX
@inproceedings{gottlob2020ijcai-fast,
title = {{Fast and Parallel Decomposition of Constraint Satisfaction Problems}},
author = {Gottlob, Georg and Okulmus, Cem and Pichler, Reinhard},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2020},
pages = {1155-1162},
doi = {10.24963/IJCAI.2020/161},
url = {https://mlanthology.org/ijcai/2020/gottlob2020ijcai-fast/}
}