7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Did you try asking the authors of the paper on hardness for 3? $\endgroup$ – Chandra Chekuri Jun 9 '16 at 16:21
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Interesting, thanks a lot for pointing it out! (Haven't read it either though.) $\endgroup$ – a3nm Nov 5 '16 at 21:21
5
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.