<p>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:
<strong>For any fixed arity bound <span class="math-container">$a \in \mathbb{N}$</span>, for any fixed <span class="math-container">$k \in \mathbb{N}$</span>, given a hypergraph <span class="math-container">$H$</span> where each hyperedge has cardinality at most <span class="math-container">$a$</span>, we can determine in PTIME in <span class="math-container">$H$</span> whether <span class="math-container">$H$</span> has generalized hypertreewidth at most <span class="math-container">$k$</span>.</strong></p>
<p>Indeed, in <a href="https://arxiv.org/abs/2002.05239" rel="nofollow noreferrer">this paper</a>, it is claimed that for any fixed <span class="math-container">$k \in \mathbb{N}$</span>, for any class of hypergraphs satisfying the so-called <em>bounded intersection property</em>, we can check in PTIME whether the generalized hypertreewidth of an input hypergraph of that class is <span class="math-container">$\leq k$</span>. 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 <a href="https://arxiv.org/abs/2309.17049" rel="nofollow noreferrer">this paper</a> which says: &quot;[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.&quot;</p>
<p>This means that, for <span class="math-container">$a = 2$</span>, the same is true on graphs: <strong>for any fixed <span class="math-container">$k \in \mathbb{N}$</span>, given a graph, we can check in PTIME if it has generalized hypertreewidth <span class="math-container">$\leq k$</span></strong>.</p>
<p>I'm still not sure about the last question: when fixing an arity bound <span class="math-container">$a \in \mathbb{N}$</span>, can we compute in PTIME, given an input hypergraph <span class="math-container">$H$</span> of arity at most <span class="math-container">$a$</span>, what is the exact generalized hypertreewidth of <span class="math-container">$H$</span>? But I would not be surprised if this is NP-hard already in the case of graphs.</p>

CC BY-SA 4.0
2024-03-13T15:41:41.453Z
PS: for the last question, a PTIME exact algorithm to compute the generalized hypertreewidth of graphs would give a PTIME constant-factor approximation of the treewidth of an input graph. This is known to be impossible conditionally to the small set expansion conjecture. Thanks to Matthias Lanzinger who made this point here: https://dbt.zulipchat.com/#narrow/stream/413942-Research/topic/Generalized.20hypertreewidth.20question/near/426319512
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2024-03-12T10:13:39.473Z
2024-03-12T10:13:39.473Z
Antoine Amarilli 'a3nm'
<p><em>Generalized hypertreewidth</em> is a generalization of <a href="https://en.wikipedia.org/wiki/Treewidth" rel="nofollow noreferrer">treewidth</a> to <a href="https://en.wikipedia.org/wiki/Hypergraph" rel="nofollow noreferrer">hypergraphs</a>. Unlike treewidth, it is not tractable, for a fixed width <span class="math-container">$k \in \mathbb{N}$</span>, given a hypergraph <span class="math-container">$H$</span>, to determine if <span class="math-container">$H$</span> has treewidth <span class="math-container">$\leq k$</span>. Indeed, it was <a href="https://arxiv.org/abs/1611.01090" rel="nofollow noreferrer">recently shown</a> (see also <a href="https://cstheory.stackexchange.com/questions/35942/complexity-of-testing-if-a-hypergraph-has-generalized-hypertreewidth-2">TCS.SE question</a>) that intractability holds already for <span class="math-container">$k=2$</span>: it is NP-hard, given an input hypergraph <span class="math-container">$H$</span>, to determine if <span class="math-container">$H$</span> has generalized hypertreewidth <span class="math-container">$\leq 2$</span>.</p>
<p>However, this hardness proof uses hypergraphs of unbounded arities (the <em>arity</em> of a hyperedge is simply its cardinality). My question: <strong>is the same true when the arity of the hyperedges of the input graph is bounded by a constant?</strong> In fact, I do not know what happens already in the case of graphs: <strong>for a fixed <span class="math-container">$k\in\mathbb{N}$</span>, can we determine in PTIME, given a graph <span class="math-container">$G$</span>, whether <span class="math-container">$G$</span> has generalized hypertreewidth <span class="math-container">$\leq k$</span>?</strong></p>
<p>Of course, when the arity is bounded to a constant <span class="math-container">$a \in \mathbb{N}$</span>, 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 <span class="math-container">$a$</span>. So one approach for tractability (suggested to me by <a href="http://www.cril.univ-artois.fr/%7Emengel/" rel="nofollow noreferrer">Stefan Mengel</a>) would be to first check in PTIME if the treewidth is <span class="math-container">$\leq k \times a$</span>: if not then the generalized hypertreewidth cannot be <span class="math-container">$\leq k$</span>, 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: <strong>for any fixed <span class="math-container">$a \in \mathbb{N}$</span>, given a hypergraph <span class="math-container">$H$</span> with edges having arity at most <span class="math-container">$a$</span>, is it PTIME to compute exactly the generalized hypertreewidth of <span class="math-container">$H$</span>?</strong></p>

CC BY-SA 4.0
2023-09-22T05:23:00.670Z
Related paper: https://arxiv.org/abs/2212.13423. For exact in this setting, I would try to generalise the Bodlaender-Kloks dynamic programming.
Laakeri
CC BY-SA 4.0
2023-09-22T06:29:28.550Z
@Laakeri: Thanks, this is indeed related. And for Bodlaender-Kloks, I agree this would probably be worth looking at.
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2023-09-23T06:10:13.147Z
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$.
Laakeri
<graph-theory><treewidth><hypergraphs>
Tractability of computing generalized hypertreewidth on bounded arity hypergraphs
Antoine Amarilli 'a3nm'
# Tractability of computing generalized hypertreewidth on bounded arity hypergraphs

(Asked by: username_0 on 2023-09-22)

*Generalized hypertreewidth* is a generalization of [treewidth](https://en.wikipedia.org/wiki/Treewidth) to [hypergraphs](https://en.wikipedia.org/wiki/Hypergraph). 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](https://arxiv.org/abs/1611.01090) (see also [TCS.SE question](https://cstheory.stackexchange.com/questions/35942/complexity-of-testing-if-a-hypergraph-has-generalized-hypertreewidth-2)) 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](http://www.cril.univ-artois.fr/%7Emengel/)) 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$?**

**Tags:** graph-theory, treewidth, hypergraphs
> **Comments:**
> **username_1**: Related paper: https://arxiv.org/abs/2212.13423. For exact in this setting, I would try to generalise the Bodlaender-Kloks dynamic programming.  
> **username_0**: @Laakeri: Thanks, this is indeed related. And for Bodlaender-Kloks, I agree this would probably be worth looking at.  
> **username_1**: 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$.  

---

## 1 answers

### Answer by username_0 on 2024-03-12. Score: 0 | Accepted answer

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](https://arxiv.org/abs/2002.05239), 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](https://arxiv.org/abs/2309.17049) 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.

> **Comments:**
> **username_0**: PS: for the last question, a PTIME exact algorithm to compute the generalized hypertreewidth of graphs would give a PTIME constant-factor approximation of the treewidth of an input graph. This is known to be impossible conditionally to the small set expansion conjecture. Thanks to Matthias Lanzinger who made this point here: https://dbt.zulipchat.com/#narrow/stream/413942-Research/topic/Generalized.20hypertreewidth.20question/near/426319512  

---

