Treewidth for hypergraphs that specify connectedness requirements

Question

This question is about an alternative definition of treewidth, called weak treewidth. It is defined on hypergraphs where hyperedges intuitively require that the connected subtrees of occurrences of the elements are connected in some way (without prescribing how), not that each pair of subtrees intersect. I am curious whether this notion has been studied, can be tested algorithmically, or is related to the usual notion of treewidth.

Formally, a hypergraph $H = (V, E)$ is a set $V$ of vertices and a set $E$ of subsets of $V$ called hyperedges. The standard notion of a tree decomposition of $H$ is a tree decomposition of the primal graph $G_H$ of $H$, in which two vertices are connected iff they co-occur in some edge (i.e., every hyperedge of $H$ gives a clique in $G_H$). In other words, a tree decomposition of $H$ is a tree $T$ and function $\mu$ mapping each node $n$ of $T$ to a subset $\mu(n)$ of vertices of $V$, such that:

• (1.) For every $v \in V$ the occurrences {$\{n \in T \mid v \in \mu(n)\}$} of $v$ in $T$ form a connected subtree of $T$,
• (2.) For every hyperedge $e \in E$ there is a node $n \in T$ such that $e \subseteq \mu(n)$.

The width of $T$ is the largest cardinality of an image of $\mu$ minus 1, and the treewidth of $H$ is the minimal width of a tree decomposition.

Now, to define weak treewidth, I define in the same way but by considering weak tree decompositions, which are just tree decompositions but weakening requirement (2.) above to the following:

• (2'.) For every hyperedge $e = \{v_1, \ldots, v_k\}$, build a graph $G_e$ on the vertices of $e$ by making $v_i$ and $v_j$ adjacent in $G_e$ if there is some tree node $n$ of $T$ such that $\{v_i,v_j\} \subseteq \mu(n)$, and require that this graph $G_e$ is connected. (The standard requirement (2.) says that $G_e$ is the complete graph on $e$.)

Equivalently, the weak treewidth of a hypergraph $H$ is the minimum treewidth of a treeification of $H$, where a treeification of $H$ is a graph obtained from $H$ by replacing each hyperedge $E$ by some connected tree over the vertices of $E$.

My question is: has this notion of weak treewidth of hypergraphs been studied before? In particular, for a constant $k$, given a hypergraph $H$, can one decide in linear time whether $H$ has treewidth $\leq k$ and if so build a weak tree decomposition, the way one does for graphs? Can the hypergraphs with weak treewidth $\leq k$ be characterized somehow?

Some initial observations:

• If $H$ is a graph (all hyperedges have arity 2), then weak treewidth and treewidth are obviously equivalent.
• The weak treewidth of $H$ is no greater than the treewidth of $H$, because a tree decomposition of $H$ is also a weak tree decomposition of $H$.
• There seems to be no converse, even with arity 3. For example, take a clique $G$, and modify it to a hypergraph $H$ by adding a fresh vertex $v$ and replacing each edge $\{x,y\}$ of $G$ by the hyperedge $\{x,y,v\}$. The hypergraph $H$ still has high treewidth, but it admits a trivial weak tree decomposition with one root bag $\{v\}$ and children $\{v,x\}$ for each vertex $x$ of $G$. (Thanks to Louis Jachiet for this observation.)
• Up to a factor of 2, condition (2') can be rephrased to (2''): for every hyperedge $e = \{v_1, \ldots, v_k\}$ in $E$, letting $T_e$ be the subset of nodes of $T$ that contain at least one element of $e$, then $T_e$ is a connected subtree of $T$. (Thanks to @Laakeri for clarifying the links between (2') and (2'').)

The motivation for this question is that this notion of treewidth seems to occur in the literature about matching patterns with variables in strings, in particular in Reidenbach and Schmid, "Patterns with bounded treewidth", I&C, 2014. (Look for "valid interpretation", or "several different ways".) Intuitively, this is because the tree decomposition represents a structure with equality requirements, and the transitivity of equality means that it suffices to represent equality across any connected subtree. It is not clear in that context whether this weaker requirement than treewidth is helpful (see "We conjecture"), but I feel like this is a natural notion in general.

Answer 1

I don't know if this notion has been studied before, but I can prove that by some standard complexity assumptions it does not have any FPT-approximation algorithm, and therefore its utility for FPT algorithms is quite limited. (There seems to be some ambiguity in the definition, in particular, the original definition of (2') and the "equivalent definition" in the fourth bullet point are actually a bit different, but my proof goes through with either of the definitions.)

Theorem: Assuming Gap-ETH (see e.g. [1] for the definition), there is no $f(k)$-approximation algorithm running in time $t(k) \cdot n^{o(k)}$ for weak treewidth for any computable functions $f$ and $t$.

Proof: By [1], the approximation hardness result of the theorem statement holds for the dominating set problem. We reduce from dominating set to weak treewidth. Let $V$ be the vertex set of the dominating set problem. First, note that dominating set is equivalent to hypergraph vertex cover problem on the hypergraph with vertices $V$ and hyperedges closed neighborhoods $N[v]$ for each $v \in V$. For our reduction, we construct a bit modified version of this hypergraph. We construct the hypergraph by introducing $2n+2$ new vertices $U = \{u_1, \ldots, u_{2n+2}\}$, having the set $V \cup U$ as the vertex set. For the hyperedges, we add a hyperedge $N[v] \cup \{u, w\}$ for each triple $v, u, w$, where $v \in V$ and $u,w \in U$.

Claim 1: If there is dominating set of size $k$, then weak treewidth of the constructed graph is at most $k$.

Proof of Claim 1: Construct a star shaped tree, where the dominating set is in a central bag, and each leaf bag contains the dominating set plus one vertex. Now, every hyperedge intersects every bag, so this satisfies (2').

Claim 2: If the weak treewidth is $k$, then there is a dominating set of size at most $k+1$.

Proof of Claim 2: If $k \ge n$ this trivially holds by selecting all of $V$, so let $k < n$. Now, by the fact that $|U| > 2k+2$ and a standard tree decomposition orientation argument with respect to $U$ there exists a single node $t \in T$ of the decomposition so that the bags of two different components of $T \setminus t$ intersect $U \setminus \mu(t)$. In particular, there are disjoint components $T_1$ and $T_2$ of $T \setminus t$ and $u,w \in U$ so that $u \in \mu(T_1) \setminus \mu(t)$ and $w \in \mu(T_2) \setminus \mu(t)$. Now, to satisfy the condition (2') for hyperedges containing $u$ and $w$, all sets $N[v]$ must intersect $\mu(t)$, and therefore $\mu(t)$ is a dominating set of size at most $k+1$.

We have a gap of 1 stemming from the ambiguous definition, but this is ok since we are anyway doing hardness of $f(k)$-approximation. $\square$

We could probably get an $n^{O(k)}$ time algorithm (which is optimal by the above theorem) by doing something similar to the Arnborg, Corneil, Proskurowski treewidth algorithm. Maybe a more interesting positive result would be an FPT-approximation algorithm when the hyperedges have bounded arity.

[1] Chalermsook, Cygan, Kortsarz, Laekhanukit, Manurangsi, Nanongkai, and Trevisan. "From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More". FOCS 2017, https://arxiv.org/abs/1708.04218.