---
title: "Computing Optimal Hypertree Decompositions with SAT"
authors:
  - "Andre Schidler"
  - "Stefan Szeider"
doi: "10.24963/ijcai.2021/196"
url: "https://ijcai.org/proceedings/2021/196"
pdf: "https://ijcai.org/proceedings/2021/0196.pdf"
venue: "Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence"
year: 2021
pages: "1418-1424"
track: "Main Track"
keywords:
  - "Constraints and SAT: Satisfiability Modulo Theories"
  - "Constraints and SAT: Constraints: Modeling, Solvers, Applications"
  - "Constraints and SAT: Constraint Satisfaction"
---

# Computing Optimal Hypertree Decompositions with SAT

Andre Schidler, Stefan Szeider

*Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence*, pages 1418-1424. DOI: [10.24963/ijcai.2021/196](https://doi.org/10.24963/ijcai.2021/196)

## 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.