Tractability of computing generalized hypertreewidth on bounded arity hypergraphs

Question

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$?

Answer 1

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.