<p>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 &quot;equivalent definition&quot; in the fourth bullet point are actually a bit different, but my proof goes through with either of the definitions.)</p>
<p>Theorem: Assuming Gap-ETH (see e.g. [1] for the definition), there is no <span class="math-container">$f(k)$</span>-approximation algorithm running in time <span class="math-container">$t(k) \cdot n^{o(k)}$</span> for weak treewidth for any computable functions <span class="math-container">$f$</span> and <span class="math-container">$t$</span>.</p>
<p>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 <span class="math-container">$V$</span> 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 <span class="math-container">$V$</span> and hyperedges closed neighborhoods <span class="math-container">$N[v]$</span> for each <span class="math-container">$v \in V$</span>. For our reduction, we construct a bit modified version of this hypergraph. We construct the hypergraph by introducing <span class="math-container">$2n+2$</span> new vertices <span class="math-container">$U = \{u_1, \ldots, u_{2n+2}\}$</span>, having the set <span class="math-container">$V \cup U$</span> as the vertex set. For the hyperedges, we add a hyperedge <span class="math-container">$N[v] \cup \{u, w\}$</span> for each triple <span class="math-container">$v, u, w$</span>, where <span class="math-container">$v \in V$</span> and <span class="math-container">$u,w \in U$</span>.</p>
<p>Claim 1: If there is dominating set of size <span class="math-container">$k$</span>, then weak treewidth of the constructed graph is at most <span class="math-container">$k$</span>.</p>
<p>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').</p>
<p>Claim 2: If the weak treewidth is <span class="math-container">$k$</span>, then there is a dominating set of size at most <span class="math-container">$k+1$</span>.</p>
<p>Proof of Claim 2: If <span class="math-container">$k \ge n$</span> this trivially holds by selecting all of <span class="math-container">$V$</span>, so let <span class="math-container">$k &lt; n$</span>. Now, by the fact that <span class="math-container">$|U| &gt; 2k+2$</span> and a standard tree decomposition orientation argument with respect to <span class="math-container">$U$</span> there exists a single node <span class="math-container">$t \in T$</span> of the decomposition so that the bags of two different components of <span class="math-container">$T \setminus t$</span> intersect <span class="math-container">$U \setminus \mu(t)$</span>.
In particular, there are disjoint components <span class="math-container">$T_1$</span> and <span class="math-container">$T_2$</span> of <span class="math-container">$T \setminus t$</span> and <span class="math-container">$u,w \in U$</span> so that <span class="math-container">$u \in \mu(T_1) \setminus \mu(t)$</span> and <span class="math-container">$w \in \mu(T_2) \setminus \mu(t)$</span>. Now, to satisfy the condition (2') for hyperedges containing <span class="math-container">$u$</span> and <span class="math-container">$w$</span>, all sets <span class="math-container">$N[v]$</span> must intersect <span class="math-container">$\mu(t)$</span>, and therefore <span class="math-container">$\mu(t)$</span> is a dominating set of size at most <span class="math-container">$k+1$</span>.</p>
<p>We have a gap of 1 stemming from the ambiguous definition, but this is ok since we are anyway doing hardness of <span class="math-container">$f(k)$</span>-approximation. <span class="math-container">$\square$</span></p>
<p>We could probably get an <span class="math-container">$n^{O(k)}$</span> 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.</p>
<p>[1] Chalermsook, Cygan, Kortsarz, Laekhanukit, Manurangsi, Nanongkai, and
Trevisan. &quot;From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More&quot;. FOCS 2017, <a href="https://arxiv.org/abs/1708.04218" rel="nofollow noreferrer">https://arxiv.org/abs/1708.04218</a>.</p>

CC BY-SA 4.0
2022-12-09T20:17:17.943Z
Thanks a lot Tuukka for your very interesting answer! Sorry, but I still don't see the nuance between (2') and the fourth bullet point -- could you clarify? Other than that, I agree with your proof, it is very nice -- though as you point out it requires the arity to be unbounded. I'm still curious also about whether there is anything in the literature about this variant on treewidth, which seems pretty natural when working with some transitive relation.
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2022-12-09T22:06:45.980Z
I think one example that shows the difference is a hypergraph with two vertices and one hyperedge containing both of the vertices. For the first definition, the width is 0 as we can have two single-vertex bags, but for the second definition the width is 1 because we need to have a bag that contains both of the vertices.
Laakeri
CC BY-SA 4.0
2022-12-10T07:51:16.520Z
Ah, I see, I thought that requiring a set of connected subtrees to be itself connected would require them to intersect like in the second definition, but I hadn't seen that two "adjacent" subtrees can form a connected subtree without intersecting, if one node of the first subtree is adjacent to one node of the other subtree. I think the definitions are equivalent up to a constant-factor increase (i.e., on a bounded-degree decomposition, replicate each bag to all the neighboring bags, and now the subtree must intersect), but you are right this was wrong. I edited the question. Thanks!
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2022-12-10T10:03:40.353Z
I think they are equivalent up to a factor of 2 because if you have a decomposition of the first type you can obtain a decomposition of the second type by subdividing each edge of the tree and placing a bag that is the union of the two adjacent bags on the subdivision node. (By the way I think the latter definition is more natural because for arity-2 hypergraphs it is equivalent to treewidth).
Laakeri
CC BY-SA 4.0
2022-12-10T14:15:26.033Z
Ah you are right a factor of 2 suffices, thanks. And you are right, the definition that preserves the link with treewidth is better for that reason, I'll edit the question to swap them.
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2022-12-07T11:05:23.893Z
2022-12-07T11:42:09.447Z
2022-12-07T11:42:09.447Z
Laakeri
<p>This question is about an alternative definition of treewidth, called <em>weak treewidth</em>. 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.</p>
<p>Formally, a hypergraph <span class="math-container">$H = (V, E)$</span> is a set <span class="math-container">$V$</span> of vertices and a set <span class="math-container">$E$</span> of subsets of <span class="math-container">$V$</span> called hyperedges. The standard notion of a <em>tree decomposition</em> of <span class="math-container">$H$</span> is a tree decomposition of the primal graph <span class="math-container">$G_H$</span> of <span class="math-container">$H$</span>, in which two vertices are connected iff they co-occur in some edge (i.e., every hyperedge of <span class="math-container">$H$</span> gives a clique in <span class="math-container">$G_H$</span>). In other words, a <em>tree decomposition</em> of <span class="math-container">$H$</span> is a tree <span class="math-container">$T$</span> and function <span class="math-container">$\mu$</span> mapping each node <span class="math-container">$n$</span> of <span class="math-container">$T$</span> to a subset <span class="math-container">$\mu(n)$</span> of vertices of <span class="math-container">$V$</span>, such that:</p>
<ul>
<li>(1.) For every <span class="math-container">$v \in V$</span> the occurrences {<span class="math-container">$\{n \in T \mid v \in \mu(n)\}$</span>} of <span class="math-container">$v$</span> in <span class="math-container">$T$</span> form a connected subtree of <span class="math-container">$T$</span>,</li>
<li>(2.) For every hyperedge <span class="math-container">$e \in E$</span> there is a node <span class="math-container">$n \in T$</span> such that <span class="math-container">$e \subseteq \mu(n)$</span>.</li>
</ul>
<p>The <em>width</em> of <span class="math-container">$T$</span> is the largest cardinality of an image of <span class="math-container">$\mu$</span> minus 1, and the <em>treewidth</em> of <span class="math-container">$H$</span> is the minimal width of a tree decomposition.</p>
<p>Now, to define <em>weak treewidth</em>, I define in the same way but by considering <em>weak tree decompositions</em>, which are just tree decompositions but weakening requirement (2.) above to the following:</p>
<ul>
<li>(2'.) For every hyperedge <span class="math-container">$e = \{v_1, \ldots, v_k\}$</span>, build a graph <span class="math-container">$G_e$</span> on the vertices of <span class="math-container">$e$</span> by making <span class="math-container">$v_i$</span> and <span class="math-container">$v_j$</span> adjacent in <span class="math-container">$G_e$</span> if there is some tree node <span class="math-container">$n$</span> of <span class="math-container">$T$</span> such that <span class="math-container">$\{v_i,v_j\} \subseteq \mu(n)$</span>, and require that this graph <span class="math-container">$G_e$</span> is connected. (The standard requirement (2.) says that <span class="math-container">$G_e$</span> is the complete graph on <span class="math-container">$e$</span>.)</li>
</ul>
<p>Equivalently, the weak treewidth of a hypergraph <span class="math-container">$H$</span> is the minimum treewidth of a <em>treeification</em> of <span class="math-container">$H$</span>, where a treeification of <span class="math-container">$H$</span> is a graph obtained from <span class="math-container">$H$</span> by replacing each hyperedge <span class="math-container">$E$</span> by some connected tree over the vertices of <span class="math-container">$E$</span>.</p>
<p>My question is: <strong>has this notion of weak treewidth of hypergraphs been studied before?</strong> In particular, for a constant <span class="math-container">$k$</span>, given a hypergraph <span class="math-container">$H$</span>, can one decide in linear time whether <span class="math-container">$H$</span> has treewidth <span class="math-container">$\leq k$</span> and if so build a weak tree decomposition, the way one does for graphs? Can the hypergraphs with weak treewidth <span class="math-container">$\leq k$</span> be characterized somehow?</p>
<p>Some initial observations:</p>
<ul>
<li>If <span class="math-container">$H$</span> is a graph (all hyperedges have arity 2), then weak treewidth and treewidth are obviously equivalent.</li>
<li>The weak treewidth of <span class="math-container">$H$</span> is no greater than the treewidth of <span class="math-container">$H$</span>, because a tree decomposition of <span class="math-container">$H$</span> is also a weak tree decomposition of <span class="math-container">$H$</span>.</li>
<li>There seems to be no converse, even with arity 3. For example, take a clique <span class="math-container">$G$</span>, and modify it to a hypergraph <span class="math-container">$H$</span> by adding a fresh vertex <span class="math-container">$v$</span> and replacing each edge <span class="math-container">$\{x,y\}$</span> of <span class="math-container">$G$</span> by the hyperedge <span class="math-container">$\{x,y,v\}$</span>. The hypergraph <span class="math-container">$H$</span> still has high treewidth, but it admits a trivial weak tree decomposition with one root bag <span class="math-container">$\{v\}$</span> and children <span class="math-container">$\{v,x\}$</span> for each vertex <span class="math-container">$x$</span> of <span class="math-container">$G$</span>. (Thanks to <a href="https://louis.jachiet.com/" rel="nofollow noreferrer">Louis Jachiet</a> for this observation.)</li>
<li>Up to a factor of 2, condition (2') can be rephrased to (2''): for every hyperedge <span class="math-container">$e = \{v_1, \ldots, v_k\}$</span> in <span class="math-container">$E$</span>, letting
<span class="math-container">$T_e$</span> be the subset of nodes of <span class="math-container">$T$</span> that contain at least one element of <span class="math-container">$e$</span>, then <span class="math-container">$T_e$</span> is a connected subtree of <span class="math-container">$T$</span>. (Thanks to @Laakeri for clarifying the links between (2') and (2'').)</li>
</ul>
<p>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, &quot;<a href="https://www.sciencedirect.com/science/article/pii/S0890540114001096" rel="nofollow noreferrer">Patterns with bounded treewidth</a>&quot;, I&amp;C, 2014. (Look for &quot;valid interpretation&quot;, or &quot;several different ways&quot;.) 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 &quot;We conjecture&quot;), but I feel like this is a natural notion in general.</p>

CC BY-SA 4.0
2022-12-06T15:36:12.883Z
Maybe one more useful observation is that the weak treewidth seems to be at most the incidence treewidth of the hypergraph (but the universal vertex example shows that incidence treewidth can be unbounded even when weak treewidth is bounded).
Laakeri
CC BY-SA 4.0
2022-12-06T15:38:42.923Z
Yes, this is indeed the case -- I think we had noticed it too but I forgot to point it out in the question. Thanks nevertheless!
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2022-12-06T15:47:03.403Z
Which in turn, should give you that bounded arity + bounded wtw gives bounded tw.
holf
CC BY-SA 4.0
2022-12-06T16:04:38.957Z
@holf actually no, see the counterexample "There seems to be no converse" of a graph having wtw 1 and arity 3 but unbounded treewidth
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2022-12-06T18:03:02.320Z
ah yes I mixed up the direction that was given by Laakeri... I was surprised both facts could coexist hence my comment, but I just read too quickly.
holf
<reference-request><graph-theory><treewidth>
Treewidth for hypergraphs that specify connectedness requirements
Antoine Amarilli 'a3nm'
# Treewidth for hypergraphs that specify connectedness requirements

(Asked by: username_0 on 2022-12-06)

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](https://louis.jachiet.com/) 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](https://www.sciencedirect.com/science/article/pii/S0890540114001096)", 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.

**Tags:** reference-request, graph-theory, treewidth
> **Comments:**
> **username_1**: Maybe one more useful observation is that the weak treewidth seems to be at most the incidence treewidth of the hypergraph (but the universal vertex example shows that incidence treewidth can be unbounded even when weak treewidth is bounded).  
> **username_0**: Yes, this is indeed the case -- I think we had noticed it too but I forgot to point it out in the question. Thanks nevertheless!  
> **username_2**: Which in turn, should give you that bounded arity + bounded wtw gives bounded tw.  
> **username_0**: @holf actually no, see the counterexample "There seems to be no converse" of a graph having wtw 1 and arity 3 but unbounded treewidth  
> **username_2**: ah yes I mixed up the direction that was given by Laakeri... I was surprised both facts could coexist hence my comment, but I just read too quickly.  

---

## 1 answers

### Answer by username_1 on 2022-12-07. Score: 3

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>.

> **Comments:**
> **username_0**: Thanks a lot Tuukka for your very interesting answer! Sorry, but I still don't see the nuance between (2') and the fourth bullet point -- could you clarify? Other than that, I agree with your proof, it is very nice -- though as you point out it requires the arity to be unbounded. I'm still curious also about whether there is anything in the literature about this variant on treewidth, which seems pretty natural when working with some transitive relation.  
> **username_1**: I think one example that shows the difference is a hypergraph with two vertices and one hyperedge containing both of the vertices. For the first definition, the width is 0 as we can have two single-vertex bags, but for the second definition the width is 1 because we need to have a bag that contains both of the vertices.  
> **username_0**: Ah, I see, I thought that requiring a set of connected subtrees to be itself connected would require them to intersect like in the second definition, but I hadn't seen that two "adjacent" subtrees can form a connected subtree without intersecting, if one node of the first subtree is adjacent to one node of the other subtree. I think the definitions are equivalent up to a constant-factor increase (i.e., on a bounded-degree decomposition, replicate each bag to all the neighboring bags, and now the subtree must intersect), but you are right this was wrong. I edited the question. Thanks!  
> **username_1**: I think they are equivalent up to a factor of 2 because if you have a decomposition of the first type you can obtain a decomposition of the second type by subdividing each edge of the tree and placing a bag that is the union of the two adjacent bags on the subdivision node. (By the way I think the latter definition is more natural because for arity-2 hypergraphs it is equivalent to treewidth).  
> **username_0**: Ah you are right a factor of 2 suffices, thanks. And you are right, the definition that preserves the link with treewidth is better for that reason, I'll edit the question to swap them.  

---

