<p>I'm afraid the answer to both of your questions is no.
Consider a graph <span class="math-container">$(V_n, E_n)$</span> with <span class="math-container">$V_n = \{1,...,n+2\}$</span> and <span class="math-container">$E = \{\{i,i+1\} | 1 \leq i \leq  n+1\} \cup \{\{i,i+2\} \mid 1 \leq i \leq n\}$</span>.</p>
<p>This describes a chain of triangles sharing an edge with their neighbors.
The treewidth of this graph is <span class="math-container">$2$</span> for any <span class="math-container">$n$</span>: you can simply have a single branch of bags <span class="math-container">$\{i,i+1,i+2\}$</span>.</p>
<p>However, its only duplicate-free tree decomposition is the one with a single bag with <span class="math-container">$n+2$</span> vertices: it is easy to show that every triangle <span class="math-container">$\{i,i+1,i+2\}$</span> must be included in a bag. In particular <span class="math-container">$\{1,2,3\}$</span> must be included in a bag <span class="math-container">$b$</span> but since the edge <span class="math-container">$\{2, 3\}$</span> must appear only once, <span class="math-container">$\{2,3,4\}$</span> must be included in <span class="math-container">$b$</span> as well. Iterating this argument shows that all vertices must be in <span class="math-container">$b$</span>.</p>
<p>At the moment I do not see a non-trivial graph class that would satisfy your property.</p>

CC BY-SA 4.0
2024-01-25T10:43:25.987Z
Thanks a lot Corto! (In fact I thought of a similar construction this morning but didn't have the time to write it yet, so you beat me to it.) One question remains: has the notion of width with these duplicate-free decompositions been studied, now that we know it's a different notion...
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2024-01-25T10:47:34.830Z
There's another question (which in fact is the one I was originally interested in): what if you impose duplicated freeness not on all edges but only on maximal cliques? More precisely it is well known that in a tree decomposition every clique, equivalently every maximal clique, must be contained in some bag. A weakly-duplicate-free tree decomposition is one where for every maximal clique the witnessing bag is unique. Can we always get a weakly-duplicate-free tree decomposition, without worsening the width (or not too much)?
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2024-02-17T22:52:20.547Z
That's an interesting question but should be asked separately. Also, if you find Corto's answer safistactory, you should accept it as an answer :-)
Vinicius dos Santos
CC BY-SA 4.0
2024-01-25T08:40:23.963Z
2024-01-25T08:40:39.190Z
2024-01-25T08:40:39.190Z
Corto
<p>In this question I am concerned with <a href="https://en.wikipedia.org/wiki/Tree_decomposition" rel="noreferrer">tree decompositions</a> of undirected graphs. Recall that a <em>tree decomposition</em> of a graph <span class="math-container">$G = (V, E)$</span> is a tree <span class="math-container">$T$</span> whose nodes are subsets of <span class="math-container">$V$</span> (called <em>bags</em>) satisfying two properties:</p>
<ul>
<li>For every edge <span class="math-container">$e = \{u, v\}$</span> of <span class="math-container">$E$</span>, there is a bag <span class="math-container">$b_e$</span> of <span class="math-container">$T$</span> containing both <span class="math-container">$u$</span> and <span class="math-container">$v$</span>, i.e., <span class="math-container">$\{u, v\} \subseteq b_e$</span></li>
<li>For every vertex <span class="math-container">$v \in V$</span>, the subset <span class="math-container">$T_v$</span> of the bags <span class="math-container">$b$</span> of <span class="math-container">$T$</span> such that <span class="math-container">$v \in b$</span> forms a connected subtree in <span class="math-container">$T$</span>.</li>
</ul>
<p>The <em>width</em> of <span class="math-container">$T$</span> is the maximal cardinality of a bag, minus one. The treewidth of <span class="math-container">$G$</span> is then the minimum width of a tree decomposition of <span class="math-container">$G$</span>.</p>
<p>My question is: <strong>what happens if, in the first condition, we impose that the witnessing bag is unique?</strong> Formally, for every edge <span class="math-container">$e \in E$</span>, there is a <strong>unique</strong> bag <span class="math-container">$b_e$</span> of <span class="math-container">$T$</span> with <span class="math-container">$e \subseteq b_e$</span>. Let us call a tree decomposition <em>duplicate-free</em> if it satisfies this stronger property. (I don't know if this has an established name.)</p>
<p>Note that any graph <span class="math-container">$G = (V, E)$</span> has a trivial duplicate-free tree decomposition with a single bag <span class="math-container">$V$</span>. The interesting question is: <strong>if a graph has treewidth <span class="math-container">$k$</span>, does it have a duplicate-free tree decomposition of width <span class="math-container">$k$</span>?</strong> Less ambitiously, can we understand how much restricting to duplicate-free tree decompostions can worsen the treewidth? Namely: is there a function <span class="math-container">$f$</span> such that every graph of treewidth <span class="math-container">$k$</span> always has a duplicate-free tree decomposition of width <span class="math-container">$f(k)$</span>?</p>
<p>An equivalent phrasing of the notion of duplicate-free tree decomposition is the following. Given two adjacent bags <span class="math-container">$b$</span> and <span class="math-container">$b'$</span> in <span class="math-container">$T$</span>, their <em>interface</em> (sometimes also called <em>separator</em>) is the intersection <span class="math-container">$b \cap b'$</span>. It is not difficult to see that if a tree decomposition is not duplicate-free then there is an edge contained in two adjacent bags. Thus, a tree decomposition is duplicate-free iff every interface of <span class="math-container">$T$</span> is an <a href="https://en.wikipedia.org/wiki/Independent_set_(graph_theory)" rel="noreferrer">independent set</a> of <span class="math-container">$G$</span>.</p>
<p>Related notions:</p>
<ul>
<li><a href="https://cstheory.stackexchange.com/questions/34089/tree-decomposition-with-clique-interfaces">This question</a> asks about the variant of treewidth where the separators must be cliques (instead of independent sets).</li>
<li><a href="https://arxiv.org/abs/2207.09993" rel="noreferrer">This paper</a> studies the complexity of computing tree decompositions where the separators have small independent set number, but does not seem to look at the case where we require them to be independent sets.</li>
</ul>

<reference-request><treewidth><clique><independent-set>
Tree decompositions with unique witness for each edge
Antoine Amarilli 'a3nm'
# Tree decompositions with unique witness for each edge

(Asked by: username_0 on 2024-01-24)

In this question I am concerned with [tree decompositions](https://en.wikipedia.org/wiki/Tree_decomposition) of undirected graphs. Recall that a *tree decomposition* of a graph $G = (V, E)$ is a tree $T$ whose nodes are subsets of $V$ (called *bags*) satisfying two properties:

* For every edge $e = \{u, v\}$ of $E$, there is a bag $b\_e$ of $T$ containing both $u$ and $v$, i.e., $\{u, v\} \subseteq b\_e$
* For every vertex $v \in V$, the subset $T\_v$ of the bags $b$ of $T$ such that $v \in b$ forms a connected subtree in $T$.

The *width* of $T$ is the maximal cardinality of a bag, minus one. The treewidth of $G$ is then the minimum width of a tree decomposition of $G$.

My question is: **what happens if, in the first condition, we impose that the witnessing bag is unique?** Formally, for every edge $e \in E$, there is a **unique** bag $b\_e$ of $T$ with $e \subseteq b\_e$. Let us call a tree decomposition *duplicate-free* if it satisfies this stronger property. (I don't know if this has an established name.)

Note that any graph $G = (V, E)$ has a trivial duplicate-free tree decomposition with a single bag $V$. The interesting question is: **if a graph has treewidth $k$, does it have a duplicate-free tree decomposition of width $k$?** Less ambitiously, can we understand how much restricting to duplicate-free tree decompostions can worsen the treewidth? Namely: is there a function $f$ such that every graph of treewidth $k$ always has a duplicate-free tree decomposition of width $f(k)$?

An equivalent phrasing of the notion of duplicate-free tree decomposition is the following. Given two adjacent bags $b$ and $b'$ in $T$, their *interface* (sometimes also called *separator*) is the intersection $b \cap b'$. It is not difficult to see that if a tree decomposition is not duplicate-free then there is an edge contained in two adjacent bags. Thus, a tree decomposition is duplicate-free iff every interface of $T$ is an [independent set](https://en.wikipedia.org/wiki/Independent_set_(graph_theory)) of $G$.

Related notions:

* [This question](https://cstheory.stackexchange.com/questions/34089/tree-decomposition-with-clique-interfaces) asks about the variant of treewidth where the separators must be cliques (instead of independent sets).
* [This paper](https://arxiv.org/abs/2207.09993) studies the complexity of computing tree decompositions where the separators have small independent set number, but does not seem to look at the case where we require them to be independent sets.

**Tags:** reference-request, treewidth, clique, independent-set


---

## 1 answers

### Answer by username_1 on 2024-01-25. Score: 4 | Accepted answer

I'm afraid the answer to both of your questions is no.
Consider a graph $(V\_n, E\_n)$ with $V\_n = \{1,...,n+2\}$ and $E = \{\{i,i+1\} | 1 \leq i \leq n+1\} \cup \{\{i,i+2\} \mid 1 \leq i \leq n\}$.

This describes a chain of triangles sharing an edge with their neighbors.
The treewidth of this graph is $2$ for any $n$: you can simply have a single branch of bags $\{i,i+1,i+2\}$.

However, its only duplicate-free tree decomposition is the one with a single bag with $n+2$ vertices: it is easy to show that every triangle $\{i,i+1,i+2\}$ must be included in a bag. In particular $\{1,2,3\}$ must be included in a bag $b$ but since the edge $\{2, 3\}$ must appear only once, $\{2,3,4\}$ must be included in $b$ as well. Iterating this argument shows that all vertices must be in $b$.

At the moment I do not see a non-trivial graph class that would satisfy your property.

> **Comments:**
> **username_0**: Thanks a lot username_1! (In fact I thought of a similar construction this morning but didn't have the time to write it yet, so you beat me to it.) One question remains: has the notion of width with these duplicate-free decompositions been studied, now that we know it's a different notion...  
> **username_0**: There's another question (which in fact is the one I was originally interested in): what if you impose duplicated freeness not on all edges but only on maximal cliques? More precisely it is well known that in a tree decomposition every clique, equivalently every maximal clique, must be contained in some bag. A weakly-duplicate-free tree decomposition is one where for every maximal clique the witnessing bag is unique. Can we always get a weakly-duplicate-free tree decomposition, without worsening the width (or not too much)?  
> **username_2**: That's an interesting question but should be asked separately. Also, if you find username_1's answer safistactory, you should accept it as an answer :-)  

---

