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, Zoltn Mikls, and Thomas Schwentick, Generalized Hypertree Decompositions: NP-Hardness and Tractable Variants, 2007Georg Gottlob, Gianluigi Greco, and Francesco Scarcello, Treewidth and Hypertree Width, 2014
Complexity of testing if a hypergraph has generalized hypertreewidth $2$
cc.complexity theory;reference request;treewidth;hypergraphs
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