3
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Interesting. Do you think that exact computation of htw via first computing ghtw and then extending it to htw is then not very well motivated? I've seen this done in a recent paper epubs.siam.org/doi/abs/10.1137/1.9781611976007.1 $\endgroup$ – Laakeri Jan 28 at 20:07
  • 2
    $\begingroup$ I did not know this paper thanks. I've only skimmed it so I cannot really give an informed comment, but from what I see their approach is motivated: their encoding is better for ghw than for hw. Now they want to also compute hw to compare with other tools. Whatever their approach, the important thing is that they have a tool. Use it and see if it fits your needs. It may be that in some cases the extra condition of hw helps you to speed up some part of your algorithm so you will be happy to have the possibility of outputting an hw decomposition. $\endgroup$ – holf Jan 29 at 7:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.