Tree decompositions with unique witness for each edge

Question

In this question I am concerned with tree decompositions 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 of $G$.

Related notions:

• This question asks about the variant of treewidth where the separators must be cliques (instead of independent sets).
• This paper 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.

Answer 1

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.

• Antoine Amarilli 'a3nm': 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': 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)?
• Vinicius dos Santos: 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 :-)