# Tractability of computing generalized hypertreewidth on bounded arity hypergraphs

Generalized hypertreewidth is a generalization of treewidth to hypergraphs. Unlike treewidth, it is not tractable, for a fixed width $$k \in \mathbb{N}$$, given a hypergraph $$H$$, to determine if $$H$$ has treewidth $$\leq k$$. Indeed, it was recently shown (see also TCS.SE question) that intractability holds already for $$k=2$$: it is NP-hard, given an input hypergraph $$H$$, to determine if $$H$$ has generalized hypertreewidth $$\leq 2$$.

However, this hardness proof uses hypergraphs of unbounded arities (the arity of a hyperedge is simply its cardinality). My question: is the same true when the arity of the hyperedges of the input graph is bounded by a constant? In fact, I do not know what happens already in the case of graphs: for a fixed $$k\in\mathbb{N}$$, can we determine in PTIME, given a graph $$G$$, whether $$G$$ has generalized hypertreewidth $$\leq k$$?

Of course, when the arity is bounded to a constant $$a \in \mathbb{N}$$, then generalized hypertreewidth is obviously related to the treewidth of the hypergraph (defined as that of its Gaifman graph, i.e., each hyperedge is encoded as a clique). Specifically, the generalized hypertreewidth is less than the treewidth and is at least the treewidth divided by $$a$$. So one approach for tractability (suggested to me by Stefan Mengel) would be to first check in PTIME if the treewidth is $$\leq k \times a$$: if not then the generalized hypertreewidth cannot be $$\leq k$$, and if yes, maybe one can compute the generalized hypertreewidth exactly in PTIME using the fact that the graph has bounded treewidth. So one related question is: for any fixed $$a \in \mathbb{N}$$, given a hypergraph $$H$$ with edges having arity at most $$a$$, is it PTIME to compute exactly the generalized hypertreewidth of $$H$$?

• Related paper: arxiv.org/abs/2212.13423. For exact in this setting, I would try to generalise the Bodlaender-Kloks dynamic programming. Sep 22 at 5:23
• @Laakeri: Thanks, this is indeed related. And for Bodlaender-Kloks, I agree this would probably be worth looking at.
– a3nm
Sep 22 at 6:29
• If you are fine with XP-algorithm instead of FPT, then the Arnborg-Corneil-Proskurowski algorithm could be generalized to get $n^{O(k \cdot r)}$ algorithm for GHTW at most $k$ on hypergraphs of rank $r$. Sep 23 at 6:10