Computing Optimal Hypertree Decompositions
André Schidler, Stefan Szeider · Society for Industrial and Applied Mathematics eBooks · 2019
We propose a new algorithmic method for computing the hypertree width of hypergraphs, and we evaluate its performance empirically. At the core of our approach lies a novel ordering based characterization of hypertree width which lends to an efficient encoding to SAT modulo Theory (SMT). We tested our algorithm on an extensive benchmark set consisting of real-world instances from various sources. Our approach outperforms state-of-the-art algorithms for hypertree width. We achieve a further speedup by a new technique that first solves a relaxation of the problem and subsequently uses the solution to guide the algorithm for solving the problem itself.