<p>A new paper from Wolfgang Fischl, Georg Gottlob, Reinhard Pichler states that it remains hard even for $k = 2$. I still haven't read it however, I am just providing the link:
<a href="https://arxiv.org/abs/1611.01090" rel="nofollow noreferrer">https://arxiv.org/abs/1611.01090</a></p>

CC BY-SA 3.0
2016-11-05T21:21:02.863Z
Interesting, thanks a lot for pointing it out! (Haven't read it either though.)
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2016-11-04T07:46:06.757Z
2016-11-04T07:53:27.943Z
2016-11-04T07:53:27.943Z
holf
<p>We do not know (to best of my knowledge).  </p>

CC BY-SA 3.0
2016-06-14T17:53:19.023Z
2016-06-14T17:53:19.023Z
Zoltan Miklos
<p>A <em>hypergraph</em> $H = (V, E)$ consists of a set of vertices $V$ and a set $E$ of <em>hyperedges</em>, i.e., subsets of $V$.</p>

<p>The <em>generalized hypertreewidth</em> (GHW) parameter is a measure of the cyclicity of a hypergraph which is a variant of its treewidth. Intuitively, it is like a tree decomposition but the width of each node is counted as the number of hyperedges required to cover it. Formally, a <em>hypertree decomposition</em> of a hypergraph is defined as a tree $T$ where each node $b \in T$ is labeled by some vertices $V(b) \subseteq V$ and $E(b) \subseteq E$. We that $T$ is a tree decomposition of $H$, namely, we impose the following on the vertex mapping:</p>

<ul>
<li>for each hyperedge $e \in E$, there is a node $b \in T$ such that $e \subseteq V(b)$</li>
<li>for each vertex $v \in V$, the set $\{b \in T \mid v \in V(b)\}$ of the vertices where $b$ occurs is a connected subtree of $T$.</li>
</ul>

<p>Further, we require the following on the edge mapping:</p>

<ul>
<li>for each node $b \in T$, the hyperedges $E(b)$ cover $V(b)$, i.e., $V(b) \subseteq \bigcup_{e \in E(b)} e$.</li>
</ul>

<p>The <em>width</em> of the decomposition $T$ is the maximum, over $b \in T$, of $|E(b)|$. The <em>GHW</em> of $H$ is the smallest $k$ such that $H$ has a generalized hypertree decomposition of size $k$.</p>

<p>My question is: <strong>Do we know the complexity of testing, given an input hypergraph $H$, whether it has GHW $\leq 2$?</strong></p>

<p>It is known that testing whether an input hypergraph has GHW $\leq 3$ is NP-hard [GMS 2007] and having GHW $=1$ is tractable because it is equivalent to being $\alpha$-acyclic as mentioned in [GGS 2014] and this is testable in linear time. I did not find any reference about whether having GHW $\leq 2$ is also tractable, or if it is already hard.</p>

<ul>
<li><p>Georg Gottlob, Zoltán Miklós, and Thomas Schwentick, "<a href="http://www.dbai.tuwien.ac.at/staff/miklos/ghw.pdf" rel="nofollow">Generalized Hypertree Decompositions: NP-Hardness and Tractable Variants</a>", 2007</p></li>
<li><p>Georg Gottlob, Gianluigi Greco, and Francesco Scarcello, "<a href="https://www.mat.unical.it/~ggreco/files/GottlobGrecoScarcello.pdf" rel="nofollow">Treewidth and Hypertree Width</a>", 2014</p></li>
</ul>

CC BY-SA 3.0
2016-06-09T16:21:57.390Z
Did you try asking the authors of the paper on hardness for 3?
Chandra Chekuri
<cc.complexity-theory><reference-request><treewidth><hypergraphs>
Complexity of testing if a hypergraph has generalized hypertreewidth $2$
Antoine Amarilli 'a3nm'
# Complexity of testing if a hypergraph has generalized hypertreewidth $2$

(Asked by: username_0 on 2016-06-09)

A *hypergraph* $H = (V, E)$ consists of a set of vertices $V$ and a set $E$ of *hyperedges*, i.e., subsets of $V$.

The *generalized hypertreewidth* (GHW) parameter is a measure of the cyclicity of a hypergraph which is a variant of its treewidth. Intuitively, it is like a tree decomposition but the width of each node is counted as the number of hyperedges required to cover it. Formally, a *hypertree decomposition* of a hypergraph is defined as a tree $T$ where each node $b \in T$ is labeled by some vertices $V(b) \subseteq V$ and $E(b) \subseteq E$. We that $T$ is a tree decomposition of $H$, namely, we impose the following on the vertex mapping:

* for each hyperedge $e \in E$, there is a node $b \in T$ such that $e \subseteq V(b)$
* for each vertex $v \in V$, the set $\{b \in T \mid v \in V(b)\}$ of the vertices where $b$ occurs is a connected subtree of $T$.

Further, we require the following on the edge mapping:

* for each node $b \in T$, the hyperedges $E(b)$ cover $V(b)$, i.e., $V(b) \subseteq \bigcup\_{e \in E(b)} e$.

The *width* of the decomposition $T$ is the maximum, over $b \in T$, of $|E(b)|$. The *GHW* of $H$ is the smallest $k$ such that $H$ has a generalized hypertree decomposition of size $k$.

My question is: **Do we know the complexity of testing, given an input hypergraph $H$, whether it has GHW $\leq 2$?**

It is known that testing whether an input hypergraph has GHW $\leq 3$ is NP-hard [GMS 2007] and having GHW $=1$ is tractable because it is equivalent to being $\alpha$-acyclic as mentioned in [GGS 2014] and this is testable in linear time. I did not find any reference about whether having GHW $\leq 2$ is also tractable, or if it is already hard.

* Georg Gottlob, Zoltán Miklós, and Thomas Schwentick, "[Generalized Hypertree Decompositions: NP-Hardness and Tractable Variants](http://www.dbai.tuwien.ac.at/staff/miklos/ghw.pdf)", 2007
* Georg Gottlob, Gianluigi Greco, and Francesco Scarcello, "[Treewidth and Hypertree Width](https://www.mat.unical.it/~ggreco/files/GottlobGrecoScarcello.pdf)", 2014

**Tags:** cc.complexity-theory, reference-request, treewidth, hypergraphs

> **Comments:**
> **username_1**: Did you try asking the authors of the paper on hardness for 3?  

---

## 2 answers

### Answer by username_2 on 2016-11-04. Score: 3 | Accepted answer

A new paper from Wolfgang Fischl, Georg Gottlob, Reinhard Pichler states that it remains hard even for $k = 2$. I still haven't read it however, I am just providing the link:
<https://arxiv.org/abs/1611.01090>

> **Comments:**
> **username_0**: Interesting, thanks a lot for pointing it out! (Haven't read it either though.)  

---

### Answer by username_3 on 2016-06-14. Score: 5

We do not know (to best of my knowledge).


---

