1
$\begingroup$

Generalized hypertreewidth is a generalization of treewidth to hypergraphs. 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 (see also TCS.SE question) 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) 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$?

$\endgroup$
3
  • 2
    $\begingroup$ Related paper: arxiv.org/abs/2212.13423. For exact in this setting, I would try to generalise the Bodlaender-Kloks dynamic programming. $\endgroup$
    – Laakeri
    Sep 22 at 5:23
  • $\begingroup$ @Laakeri: Thanks, this is indeed related. And for Bodlaender-Kloks, I agree this would probably be worth looking at. $\endgroup$
    – a3nm
    Sep 22 at 6:29
  • $\begingroup$ 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$. $\endgroup$
    – Laakeri
    Sep 23 at 6:10

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.