Computing Optimal Hypertree Decompositions with SAT
Abstract
Hypertree width is a prominent hypergraph invariant with many algorithmic applications in constraint satisfaction and databases. We propose a novel characterization for hypertree width in terms of linear elimination orderings. We utilize this characterization to generate a new SAT encoding that we evaluate on an extensive set of benchmark instances. We compare it to state-of-the-art exact methods for computing optimal hypertree width. Our results show that the encoding based on the new characterization is not only significantly more compact than known encodings but also outperforms the other methods.
Cite
Text
Schidler and Szeider. "Computing Optimal Hypertree Decompositions with SAT." International Joint Conference on Artificial Intelligence, 2021. doi:10.24963/IJCAI.2021/196Markdown
[Schidler and Szeider. "Computing Optimal Hypertree Decompositions with SAT." International Joint Conference on Artificial Intelligence, 2021.](https://mlanthology.org/ijcai/2021/schidler2021ijcai-computing/) doi:10.24963/IJCAI.2021/196BibTeX
@inproceedings{schidler2021ijcai-computing,
title = {{Computing Optimal Hypertree Decompositions with SAT}},
author = {Schidler, André and Szeider, Stefan},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2021},
pages = {1418-1424},
doi = {10.24963/IJCAI.2021/196},
url = {https://mlanthology.org/ijcai/2021/schidler2021ijcai-computing/}
}