Complexity of computing the simplicial width of a graph

Question

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):

• computing the treewidth of an input graph (even without a decomposition) is NP-complete (open access link);
• for any fixed $k \in \mathbb{N},ドル computing a tree decomposition of width $\leq k$ can be done in linear time (open access link).

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).

Answer 1

So as David Eppstein says here, this is PTIME and follows from the article by Tarjan that is cited in the current question. Here are more details on why this holds.

For $G=(V,E)$ a graph and $U\subseteq V$, denote by $G[U]$ the subgraph of $G$ induced by $U$. (All subgraphs will be induced in this post.) A set $U\subseteq V$ is a separator if $G[V\setminus U]$ is disconnected, and it is a clique separator if additionally it is a clique (we allow the empty set as a clique, so that disconnected graphs always have $\emptyset$ as a clique separator). The graph $G$ is prime if it has no clique separator. A prime subgraph of $G$ is an induced subgraph $G[U]$ that is prime. Then we have:

Proposition: The simplicial width of $G$ is equal to the size (number of nodes) of the largest prime subgraph of $G$. Moreover, given $G$, we can compute in PTIME a simplicial decomposition achieving this width.

Proof: First we show that the simplicial width of $G$ is at least the size of the largest prime subgraph of $G$. To show this, we prove that for any simplicial decomposition $(T,\lambda)$ of $G$ and prime subgraph $G[U]$ of $G$, there must be a bag $n$ of $T$ such that $U \subseteq \lambda(n)$. Indeed, assume by contradiction that this is false. Let $U'$ be a maximal (for inclusion) subset of $U$ that is included in some bag of the decomposition, call $n$ this bag (so $U' \subseteq \lambda(n)$). From $n$ we can explore $T$ until we find a node $n'$ that contains some $z\in U\setminus U'$, let $n=n_1,\ldots, n_m = n'$ be the path of nodes of $T$ encountered in this exploration. Then for 1ドル \leq j \leq m-1$ we have $\lambda(n_j)\cap U \subseteq U'$. Now, since $z\notin U'$, by maximality of $U'$ there must be some $z'\in U'$ such that $z' \notin \lambda(n')$. But now, letting $C = \lambda(n') \cap \lambda(n_{m-1})$, we see that $C \cap U$ is a clique separator of $G[U]$ (since it separates $z$ and $z'$), contradicting that $G[U]$ is prime.

Second, we show how to build a simplicial decomposition with the claimed width. In his article Tarjan proves that given $G$, we can find in PTIME a clique separator. We then build a simplicial decomposition of $G$ where all bags are subgraphs of prime graphs of $G$ inductively as follows. If $G$ is prime we take the decomposition with a single bag that contains all the vertices of $G$ and we are done. Otherwise, find a clique clique separator $C$ of $G$ in PTIME, and so we have $A,C,B$ a partition of $B$ with $G = G[A\cup C] \cup G[C\cup B]$ and there is no edge between vertices of $A$ and vertices of $B$. Inductively build simplicial decompositions $T_1$ for $G[A\cup C]$ and $T_2$ for $G[C \cup B]$ whose bags are respectively subgraphs of prime graphs of $G[A\cup C]$ and $G[C\cup B]$, hence of $G$. Since $C$ is a clique, by the running intersection property of tree decompositions, there must be bags $n_1$ of $T_1$ and $n_2$ of $T_2$ that both contain $C$. Then we can simply build a simplicial decomposition of $G$ by connecting $n_1$ and $n_2$. Again this tree decomposition ensures that every bag is a subgraph of a prime graph of $G$. Hence, overall, the width of this decomposition is the size of the largest prime subgraph of $G$ (using the fact that if $G[U]$ is a prime subgraph of $G$ then we must have $U\subseteq A\cup C$ or $U\subseteq C\cup B$).