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 \lambda(n)\}$ forms a connected subtree of $T$.

For my purposes (namely, showing the tractability of model-checking for a particular logical fragment), and following my earlier question, I am interested in a restricted kind of tree decompositions, that satisfies an additional condition. I call a simplicial decomposition 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$, 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 a simplicial decomposition is $max_{n \in T}|\lambda(n)|-1$ and the simplicial width of $G$ is the minimal width of a simplicial decomposition. Note that, of course, the simplicial width of $G$ is necessarily greater than its treewidth in the usual sense.

My question is to know whether the complexity of the following two problems is known:

  • computing the simplicial width together with a simplicial decomposition, i.e., given as input an undirected graph $G$, compute the simplicial width $w$ of $G$ and a simplicial decomposition of width $w$;
  • computing, for a fixed width, a simplicial decomposition of that width, i.e., for a fixed constant $k \in \mathbb{N}$, given as input an undirected graph $G$, computing a simplicial decomposition of width $\leq k$ if one exists, and outputting "no" otherwise.

For the usual notion of treewidth, the known complexities are the following (but they don't give bound for simplicial width):

The name of simplicial decomposition is introduced in "Simplicial decompositions of graphs: a survey of applications", Reinhard Diestel, Discrete Mathematics 75 (1-3): 121-144 1989 and is the same as that of "decomposition by clique separators" in "Decomposition by clique separators", Robert E. Tarjan, Discrete Mathematics 55 (2): 221–232, 1985. However, it seems that the notion of simplicial width is not studied here. There is a similar notion of clique minimal separator decomposition for which a quadratic bound is known (here and here) but it doesn't seem to be exactly the same problem (I think it minimizes the size of the separators between bags, not the size of the bags).

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.