3
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ 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). $\endgroup$
    – Laakeri
    Dec 6, 2022 at 15:36
  • $\begingroup$ 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! $\endgroup$
    – a3nm
    Dec 6, 2022 at 15:38
  • $\begingroup$ Which in turn, should give you that bounded arity + bounded wtw gives bounded tw. $\endgroup$
    – holf
    Dec 6, 2022 at 15:47
  • $\begingroup$ @holf actually no, see the counterexample "There seems to be no converse" of a graph having wtw 1 and arity 3 but unbounded treewidth $\endgroup$
    – a3nm
    Dec 6, 2022 at 16:04
  • 1
    $\begingroup$ 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. $\endgroup$
    – holf
    Dec 6, 2022 at 18:03

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – a3nm
    Dec 9, 2022 at 20:17
  • $\begingroup$ 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. $\endgroup$
    – Laakeri
    Dec 9, 2022 at 22:06
  • $\begingroup$ 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! $\endgroup$
    – a3nm
    Dec 10, 2022 at 7:51
  • 1
    $\begingroup$ 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). $\endgroup$
    – Laakeri
    Dec 10, 2022 at 10:03
  • $\begingroup$ 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. $\endgroup$
    – a3nm
    Dec 10, 2022 at 14:15

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.