Computing hypergraph width measures exactly

Hypergraph width measures are important in studying the complexity of constraint satisfaction problems (CSPs). We present a general exact exponential algorithm for a large variety of these measures. As a consequence, we obtain algorithms which, for a hypergraph H on n vertices and m   hyperedges, compute its generalized hypertree-width in time O⁎(n2)O⁎(2n) and its fractional hypertree-width in time O(n1.734601⋅m)O(1.734601n⋅m).3

► We present a general exact exponential algorithm for the f-width of a hypergraph. ► Our algorithm works for any monotone width function f. ► This results in the currently fastest algorithm for generalized hypertree-width. ► Also this results in the currently fastest algorithm for fractional hypertree-width.