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, 2023 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, 2023 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, 2023 at 6:10

1 Answer 1

0
$\begingroup$

I must confess I did not find the time to look into the references by @Laakeri, but looking again at my question and some references I found since then, I think the following is true: For any fixed arity bound $a \in \mathbb{N}$, for any fixed $k \in \mathbb{N}$, given a hypergraph $H$ where each hyperedge has cardinality at most $a$, we can determine in PTIME in $H$ whether $H$ has generalized hypertreewidth at most $k$.

Indeed, in this paper, it is claimed that for any fixed $k \in \mathbb{N}$, for any class of hypergraphs satisfying the so-called bounded intersection property, we can check in PTIME whether the generalized hypertreewidth of an input hypergraph of that class is $\leq k$. But of course hypergraphs with constant arity have in particular the bounded intersection property, because the intersection of two hyperedges is no larger than a single hyperedge. This result is also mentioned in this paper which says: "[computing generalized hypertreewidth] is in XP if we restrict the problem to so-called (c, d)-hypergraphs, i.e., hypergraphs where any intersection of at least c edges has cardinality at most d."

This means that, for $a = 2$, the same is true on graphs: for any fixed $k \in \mathbb{N}$, given a graph, we can check in PTIME if it has generalized hypertreewidth $\leq k$.

I'm still not sure about the last question: when fixing an arity bound $a \in \mathbb{N}$, can we compute in PTIME, given an input hypergraph $H$ of arity at most $a$, what is the exact generalized hypertreewidth of $H$? But I would not be surprised if this is NP-hard already in the case of graphs.

$\endgroup$
1
  • $\begingroup$ PS: for the last question, a PTIME exact algorithm to compute the generalized hypertreewidth of graphs would give a PTIME constant-factor approximation of the treewidth of an input graph. This is known to be impossible conditionally to the small set expansion conjecture. Thanks to Matthias Lanzinger who made this point here: dbt.zulipchat.com/#narrow/stream/413942-Research/topic/… $\endgroup$
    – a3nm
    Mar 13 at 15:41

Your Answer

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

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