7
$\begingroup$

Let $G=(V,E)$ be a finite undirected graph. A 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. 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.

$\endgroup$
  • 1
    $\begingroup$ I think these decompositions correspond to what Diestel calls "simplicial decompositions" (see sciencedirect.com/science/article/pii/0012365X89900848) but I don't know if the width is considered in this part of the literature. $\endgroup$ – Florent Foucaud Mar 16 '16 at 22:34
  • $\begingroup$ Because of this name, perhaps "simplicial width" or "simplicial treewidth" could be appropriate names for this width parameter? $\endgroup$ – Florent Foucaud Mar 17 '16 at 8:25
10
$\begingroup$

See "Decomposition by clique separators", Robert E. Tarjan, Discrete Mathematics 55 (2): 221–232, 1985.

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.