babylonpolice.com

A minimal separator of a graph $G$ is a set $S \subseteq V(G)$ such that
there exist vertices $a,b \in V(G) \setminus S$ with the property that $S$
separates $a$ from $b$ in $G$, but no proper subset of $S$ does. For an integer
$k\ge 0$, we say that a minimal separator is $k$-simplicial if it can be
covered by $k$ cliques and denote by $\mathcal{G}_k$ the class of all graphs in
which each minimal separator is $k$-simplicial. We show that for each $k \geq
0$, the class $\mathcal{G}_k$ is closed under induced minors, and we use this
to show that the Maximum Weight Stable Set problem can be solved in polynomial
time for $\mathcal{G}_k$. We also give a complete list of minimal forbidden
induced minors for $\mathcal{G}_2$. Next, we show that, for $k \geq 1$, every
nonnull graph in $\mathcal{G}_k$ has a $k$-simplicial vertex, i.e., a vertex
whose neighborhood is a union of $k$ cliques; we deduce that the Maximum Weight
Clique problem can be solved in polynomial time for graphs in $\mathcal{G}_2$.
Further, we show that, for $k \geq 3$, it is NP-hard to recognize graphs in
$\mathcal{G}_k$; the time complexity of recognizing graphs in $\mathcal{G}_2$
is unknown. We also show that the Maximum Clique problem is NP-hard for graphs
in $\mathcal{G}_3$. Finally, we prove a decomposition theorem for diamond-free
graphs in $\mathcal{G}_2$ (where the diamond is the graph obtained from $K_4$
by deleting one edge), and we use this theorem to obtain polynomial-time
algorithms for the Vertex Coloring and recognition problems for diamond-free
graphs in $\mathcal{G}_2$, and improved running times for the Maximum Weight
Clique and Maximum Weight Stable Set problems for this class of graphs.