<p>See <a href="http://dx.doi.org/10.1016/0012-365X(85)90051-2">"Decomposition by clique separators", Robert E. Tarjan, <em>Discrete Mathematics</em> 55 (2): 221–232, 1985</a>.</p>

<p>If I understand correctly, your notion of width is essentially the size of the largest piece in Tarjan's decomposition.</p>

CC BY-SA 3.0
2016-03-16T17:54:01.347Z
2016-03-16T17:54:01.347Z
David Eppstein
<p>Let $G=(V,E)$ be a finite undirected graph. A <em><a href="https://en.wikipedia.org/wiki/Tree_decomposition">tree decomposition</a></em> $(T,\lambda)$ of $G$ is a tree $T$ with labeling function $\lambda : T \to 2^{V}$ such that:</p>

<ol>
<li>For every edge $\{v_1,v_2\} \in E$, there exists a node $n$ of $T$ such that $v_1,v_2 \in \lambda(n)$.</li>
<li>For every vertex $v \in V$, the set $\{n \in T \mid v \in n\}$ forms a connected subtree of $T$.</li>
</ol>

<p>For my purposes (namely, showing the tractability of model-checking for a particular logical fragment), I am interested in a restricted kind of tree decompositions, that satisfies an additional condition. I call a <em>tree-decomposition with clique interfaces</em> a tree decomposition $(T,\lambda)$ of $G$ that respects the following additional property:</p>

<ul>
<li>For every two adjacent nodes $n_1$ and $n_2$ of the tree decomposition $T$, we require that the <em>interface</em> $\lambda(n_1) \cap \lambda(n_2)$ forms a clique in $G$. In other words, for every pair of distinct elements $a,b$ occurring both in $n_1$ and $n_2$, we must have $\{a, b\} \in E$.</li>
</ul>

<p>As usual, the <em>width</em> of such a decomposition is $max_{n \in T}|\lambda(n)|-1$ and the <em>width</em> of $G$ is the minimal width of such a decomposition.
Note that, of course, the width of $G$ according to this definition is necessarily greater than its treewidth in the usual sense.</p>

<p>My question is to know <strong>if this notion of width has already been studied and has an established name</strong>. In particular, I am interested in alternative characterization of graphs whose width is low in this sense, in the complexity of computing it, etc.</p>

<p>This could be related to the notion of <em><a href="http://dmg.tuwien.ac.at/drmota/DAHeinz.apdf">$k$-trees</a></em>. In k-trees, we impose in tree decompositions that $\lambda(n)$ forms a clique for all $n$ and that the interfaces are of size $k$. However not all graphs have such a decomposition, while for the notion that I propose, all graphs would have a decomposition (at worst the trivial one with width $|V|-1$) so it looks like this notion could have been studied in a general context.</p>

CC BY-SA 3.0
2016-03-16T22:34:46.550Z
I think these decompositions correspond to what Diestel calls "simplicial decompositions" (see http://www.sciencedirect.com/science/article/pii/0012365X89900848) but I don't know if the width is considered in this part of the literature.
Florent Foucaud
CC BY-SA 3.0
2016-03-17T08:25:46.863Z
Because of this name, perhaps "simplicial width" or "simplicial treewidth" could be appropriate names for this width parameter?
Florent Foucaud
<reference-request><graph-theory><clique><treewidth>
Tree-decomposition with clique interfaces
M.Monet
# Tree-decomposition with clique interfaces

(Asked by: username_0 on 2016-03-16)

Let $G=(V,E)$ be a finite undirected graph. A *[tree decomposition](https://en.wikipedia.org/wiki/Tree_decomposition)* $(T,\lambda)$ of $G$ is a tree $T$ with labeling function $\lambda : T \to 2^{V}$ such that:

1. For every edge $\{v\_1,v\_2\} \in E$, there exists a node $n$ of $T$ such that $v\_1,v\_2 \in \lambda(n)$.
2. For every vertex $v \in V$, the set $\{n \in T \mid v \in n\}$ forms a connected subtree of $T$.

For my purposes (namely, showing the tractability of model-checking for a particular logical fragment), I am interested in a restricted kind of tree decompositions, that satisfies an additional condition. I call a *tree-decomposition with clique interfaces* a tree decomposition $(T,\lambda)$ of $G$ that respects the following additional property:

* For every two adjacent nodes $n\_1$ and $n\_2$ of the tree decomposition $T$, we require that the *interface* $\lambda(n\_1) \cap \lambda(n\_2)$ forms a clique in $G$. In other words, for every pair of distinct elements $a,b$ occurring both in $n\_1$ and $n\_2$, we must have $\{a, b\} \in E$.

As usual, the *width* of such a decomposition is $max\_{n \in T}|\lambda(n)|-1$ and the *width* of $G$ is the minimal width of such a decomposition.
Note that, of course, the width of $G$ according to this definition is necessarily greater than its treewidth in the usual sense.

My question is to know **if this notion of width has already been studied and has an established name**. In particular, I am interested in alternative characterization of graphs whose width is low in this sense, in the complexity of computing it, etc.

This could be related to the notion of *[$k$-trees](http://dmg.tuwien.ac.at/drmota/DAHeinz.apdf)*. In k-trees, we impose in tree decompositions that $\lambda(n)$ forms a clique for all $n$ and that the interfaces are of size $k$. However not all graphs have such a decomposition, while for the notion that I propose, all graphs would have a decomposition (at worst the trivial one with width $|V|-1$) so it looks like this notion could have been studied in a general context.

**Tags:** reference-request, graph-theory, clique, treewidth

> **Comments:**
> **username_1**: I think these decompositions correspond to what Diestel calls "simplicial decompositions" (see http://www.sciencedirect.com/science/article/pii/0012365X89900848) but I don't know if the width is considered in this part of the literature.  
> **username_1**: Because of this name, perhaps "simplicial width" or "simplicial treewidth" could be appropriate names for this width parameter?  

---

## 1 answers

### Answer by username_2 on 2016-03-16. Score: 10 | Accepted answer

See ["Decomposition by clique separators", Robert E. Tarjan, *Discrete Mathematics* 55 (2): 221–232, 1985](http://dx.doi.org/10.1016/0012-365X(85)90051-2).

If I understand correctly, your notion of width is essentially the size of the largest piece in Tarjan's decomposition.


---

