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", 2007
Georg Gottlob, Gianluigi Greco, and Francesco Scarcello, "Treewidth and Hypertree Width", 2014
