# 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. Commented Sep 22, 2023 at 5:23
• @Laakeri: Thanks, this is indeed related. And for Bodlaender-Kloks, I agree this would probably be worth looking at.
– a3nm
Commented Sep 22, 2023 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$. Commented Sep 23, 2023 at 6:10

I must confess I did not find the time to look into the references by @Laakeri, but looking again at my question and some references I found since then, I think the following is true: For any fixed arity bound $$a \in \mathbb{N}$$, for any fixed $$k \in \mathbb{N}$$, given a hypergraph $$H$$ where each hyperedge has cardinality at most $$a$$, we can determine in PTIME in $$H$$ whether $$H$$ has generalized hypertreewidth at most $$k$$.
Indeed, in this paper, it is claimed that for any fixed $$k \in \mathbb{N}$$, for any class of hypergraphs satisfying the so-called bounded intersection property, we can check in PTIME whether the generalized hypertreewidth of an input hypergraph of that class is $$\leq k$$. But of course hypergraphs with constant arity have in particular the bounded intersection property, because the intersection of two hyperedges is no larger than a single hyperedge. This result is also mentioned in this paper which says: "[computing generalized hypertreewidth] is in XP if we restrict the problem to so-called (c, d)-hypergraphs, i.e., hypergraphs where any intersection of at least c edges has cardinality at most d."
This means that, for $$a = 2$$, the same is true on graphs: for any fixed $$k \in \mathbb{N}$$, given a graph, we can check in PTIME if it has generalized hypertreewidth $$\leq k$$.
I'm still not sure about the last question: when fixing an arity bound $$a \in \mathbb{N}$$, can we compute in PTIME, given an input hypergraph $$H$$ of arity at most $$a$$, what is the exact generalized hypertreewidth of $$H$$? But I would not be surprised if this is NP-hard already in the case of graphs.