When is hypertree width more useful than generalized hypertree width?

Question

In analysis of CSPs, there are three width notions that are analogous to treewidth: hypertree width (hw), generalized hypertree width (ghw) and fractional hypertree width (fhw). Moreover the inequalities $\text{fhw} \le \text{ghw} \le \text{hw}$ are known. The only motivation for hw instead of ghw that I have seen is that there is an XP algorithm for computing hw, but not for computing ghw. Is there any other motivation for hw instead of ghw? More concretely:

What algorithmic results there are that work when a hypertree decomposition of the smallest width is given, but not when a generalized hypertreewidth decomposition of the smallest width is given?

Answer 1

Every XP/FPT algorithm parametrized by htw also gives an XP/FPT algorithm parametrized by ghtw (provided that the decomposition is given in the input) since there is a linear relation between ghw and hw [1]: $\mathsf{hw} \leq 3\mathsf{ghw}+1$. So basically, you can see hw as a easier to compute constant approximation of ghw.

I am not aware however of problems that are XP when parametrized by hw but not by fhw.

Side note however: if you are only interested in problems when the input is a CSP (with positive encodings) / Database of bounded (f)hw, then an XP algorithm for htw will often give you an XP algorithm for fhw.

Indeed, if the algorithm is XP for hw, then it is polynomial on $\alpha$-acyclic hypergraphs, that is, hypergraphs of hw $1$. Now, if you perform the join of the guards inside each bag of the (fractional / generalized) hw decomposition then you get a new CSP / Databases that is $\alpha$-acyclic. Moreover, each new relation is of XP size in the original DB/CSP. Now if you can rewrite your problem on this new database, this directly give you an XP algorithm for fhw.

[1] I. Adler, G. Gottlob, and M. Grohe. Hypertree width and related hy-pergraph invariants.European Journal of Combinatorics, 28(8):2167– 2181, 2007. 24