Lovász–Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs

Abstract

We study the Lovász–Schrijver lift-and-project operator (${{\mathrm{\text {LS}}}}_+$) based on the cone of symmetric, positive semidefinite matrices, applied to the fractional stable set polytope of graphs. The problem of obtaining a combinatorial characterization of graphs for which the ${{\mathrm{\text {LS}}}}_+$-operator generates the stable set polytope in one step has been open since 1990. We call these graphs ${{{\mathrm{\text {LS}}}}}_+$-perfect. In the current contribution, we pursue a full combinatorial characterization of ${{{\mathrm{\text {LS}}}}}_+$-perfect graphs and make progress towards such a characterization by establishing a new, close relationship among ${{{\mathrm{\text {LS}}}}}_+$-perfect graphs, near-bipartite graphs and a newly introduced concept of full-support-perfect graphs.

1 Introduction

The notion of a perfect graph was introduced by Berge in the early 1960s [5]. A graph is called perfect if each of its induced subgraphs has chromatic number equal to the size of a maximum cardinality clique in the subgraph. Perfect graphs have caught the attention of many researchers in the area and inspired numerous very interesting contributions to the literature for the past fifty years. One of the main results in the seminal paper of Grötschel et al. [20] is that perfect graphs constitute a graph class where the Maximum Weight Stable Set Problem (MWSSP) can be solved in polynomial-time. Some years later, the same authors proved a very beautiful, related result which connects a purely graph theoretic notion to polyhedrality of a typically nonlinear convex relaxation and to the integrality and equality of two fundamental polytopes:

Theorem 1

(Grötschel et al. [20, 21]) For every graph G, the following are equivalent:

• (1) $G \text { is perfect;}$

• (2) ${{\mathrm{\text {STAB}}}}(G)={{\mathrm{\text {CLIQUE}}}}(G);$

• (3) $\text {TH}(G)={{\mathrm{\text {STAB}}}}(G);$

• (4) $\text {TH}(G)={{\mathrm{\text {CLIQUE}}}}(G);$

• (5) $\text {TH}(G) \text { is polyhedral.}$

In the above theorem, ${{\mathrm{\text {STAB}}}}(G)$ is the stable set polytope of G, ${{\mathrm{\text {CLIQUE}}}}(G)$ is its clique relaxation and $\text {TH}(G)$ is the theta body of G defined by Lovász [27].

In the early 1990s, Lovász and Schrijver [28] introduced the semidefinite relaxation ${{{\mathrm{\text {LS}}}}}_+(G)$ (${{\mathrm{\text {LS}}}}_+$ operator was originally denoted by $N_+$ in [28]) of ${{\mathrm{\text {STAB}}}}(G)$ which is stronger than $\text {TH}(G)$. Following the same line of reasoning used for perfect graphs, they proved that MWSSP can be solved in polynomial-time for the class of graphs for which ${{{\mathrm{\text {LS}}}}}_+(G)={{\mathrm{\text {STAB}}}}(G)$. We call these graphs ${{{\mathrm{\text {LS}}}}}_+$-perfect graphs (originally, the authors called these graphs $N_+$-perfect [7]). The set of ${{{\mathrm{\text {LS}}}}}_+$-perfect graphs is known to contain many rich and interesting classes of graphs (e.g., perfect graphs, t-perfect graphs, wheels, anti-holes, near-bipartite graphs) and their clique sums. However, no combinatorial characterization of ${{{\mathrm{\text {LS}}}}}_+$-perfect graphs have been obtained so far.

There are many studies of various variants of lift-and-project operators applied to the relaxations of the stable set problem (see for instance, [9, 15, 16, 18, 19, 22–24, 26, 31, 34]). Why study ${{\mathrm{\text {LS}}}}_+$-perfect graphs? For example, if we want to characterize the largest family of graphs for which MWSSP can be solved in polynomial-time, then perhaps, we should pick a tractable relaxation of ${{\mathrm{\text {STAB}}}}(G)$ which is as strong as possible. This reasoning would suggest that, we should focus on the strongest, tractable lift-and-project operator and reiterate it as much as possible while maintaining tractability of the underlying relaxation. Even though the (lower bound) analysis for the strongest lift-and-project operators is typically very challenging, some considerable amount of work on the behaviour of the strongest lift-and-project operators applied to the stable set problem already exists (see [1] and the references therein). In the spectrum of strong lift-and-project operators which utilize positive semidefiniteness constraints, given the above results of Grötschel et al. [20, 21], it seems clear to us that we should pick an operator which is at least as strong as $\text {TH}(G)$. Among many of the convex relaxations that are closely related to $\text {TH}(G)$ but stronger, $\text {TH}(G)$ continues to emerge as the central object with quite special mathematical properties (see [10] and the references therein). Given that the operator ${{\mathrm{\text {LS}}}}_+(G)$ can be defined as the intersection of the matrix-space liftings of the odd-cycle polytope of G and the theta body of G, by definition, ${{\mathrm{\text {LS}}}}_+(G)$ encodes and retains very interesting combinatorial information about the graph G. Then, the next question is why not focus on iterated (hence stronger) operator ${{\mathrm{\text {LS}}}}_+^k$ for $k\ge 2$ but k small enough to maintain tractability? The answer to this is related to the above; but, it is a bit more subtle: in the lifted, matrix-space representation of ${{\mathrm{\text {LS}}}}_+$, if we remove the positive semidefiniteness constraint, we end up with the lifting of the operator ${{\mathrm{\text {LS}}}}$ (defined later). In this lifted matrix space, if we remove the restriction that the matrix be symmetric, we end up with the lifting of a weaker relaxation ${{\mathrm{\text {LS}}}}_0$. ${{\mathrm{\text {LS}}}}_0^k$ retains many interesting combinatorial properties of G, see [24, 25]. Moreover, Lovász and Schrijver proved that for every graph G, ${{\mathrm{\text {LS}}}}_0(G)={{\mathrm{\text {LS}}}}(G)$. However, this property does not generalize to the iterated operators ${{\mathrm{\text {LS}}}}_0^k$, ${{\mathrm{\text {LS}}}}^k$, even for $k=2$, even if we require that the underlying graph G be perfect (see [2, 3]). Therefore, ${{\mathrm{\text {LS}}}}_+$ has many of the desired attributes for this purpose.

One of our main goals in this line of research is to obtain a characterization of ${{{\mathrm{\text {LS}}}}}_+$-perfect graphs similar to the one given in Theorem 1 for perfect graphs. More precisely, we would like to find an appropriate polyhedral relaxation of ${{\mathrm{\text {STAB}}}}(G)$ playing the role of ${{\mathrm{\text {CLIQUE}}}}(G)$ in Theorem 1, when we replace $\text {TH}(G)$ by ${{{\mathrm{\text {LS}}}}}_+(G)$. In [7] we introduced the polyhedral relaxation ${{\mathrm{\text {NB}}}}(G)$ of ${{\mathrm{\text {STAB}}}}(G)$, which is, to the best of our knowledge, the tightest polyhedral relaxation of ${{{\mathrm{\text {LS}}}}}_+(G)$. Roughly speaking, ${{\mathrm{\text {NB}}}}(G)$ is defined by the family of facets of stable set polytopes of a family of graphs that are built from near-bipartite graphs by using simple operations so that the stable set polytope of the resulting graph does not have any facets outside the class of facets which define the stable set polytope of near-bipartite graphs (for a precise definition of ${{\mathrm{\text {NB}}}}(G)$, see Sect. 2). In our quest to obtain the desired characterization of ${{{\mathrm{\text {LS}}}}}_+$-perfect graphs, ${{\mathrm{\text {NB}}}}(G)$ is our current best guess for replacing ${{\mathrm{\text {CLIQUE}}}}(G)$ in Theorem 1. More specifically, we conjecture that the next four statements are equivalent.

Conjecture 2

For every graph G, the following four statements are equivalent:

• (1) ${{\mathrm{\text {STAB}}}}(G)={{\mathrm{\text {NB}}}}(G)$;

• (2) ${{{\mathrm{\text {LS}}}}}_+(G)={{\mathrm{\text {STAB}}}}(G)$;

• (3) ${{{\mathrm{\text {LS}}}}}_+(G)={{\mathrm{\text {NB}}}}(G)$;

• (4) ${{{\mathrm{\text {LS}}}}}_+(G)$ is polyhedral.

Verifying the validity of Conjecture 2 is equivalent to determining the validity of the following two statements:

Conjecture 3

For every graph G, if ${{{\mathrm{\text {LS}}}}}_+(G)$ is polyhedral then ${{\mathrm{\text {STAB}}}}(G)={{\mathrm{\text {NB}}}}(G)$.

Conjecture 4

For every graph G, if ${{{\mathrm{\text {LS}}}}}_+(G)={{\mathrm{\text {STAB}}}}(G)$ then ${{\mathrm{\text {STAB}}}}(G)={{\mathrm{\text {NB}}}}(G)$.

In [6], we made some progress towards proving Conjecture 3, by presenting an infinite family of graphs for which it holds. Recently, Conjecture 4 was verified for web graphs [17]. In this contribution, we prove that Conjecture 4 holds for a class of graphs called ${\mathrm {fs}}$ -perfect graphs that stand for full-support-perfect graphs. This graph family was originally defined in [29] and includes the set of near-perfect graphs previously defined by Shepherd in [32].

One of the main difficulties in obtaining a good combinatorial characterization for ${{{\mathrm{\text {LS}}}}}_+$-perfect graphs is that the lift-and-project operator ${{{\mathrm{\text {LS}}}}}_+$ (and many related operators) can behave sporadically under many well-studied graph-minor operations (see [16, 26]). Therefore, in the study of ${{{\mathrm{\text {LS}}}}}_+$-perfect graphs we are faced with the problem of constructing suitable graph operations and then deriving certain monotonicity or loose invariance properties under such graph operations. In this context, we present two operations which preserve ${{{\mathrm{\text {LS}}}}}_+$-imperfection in graphs.

In the next section, we begin with notation and preliminary results that will be used throughout the paper. We also state our main characterization conjecture on ${{{\mathrm{\text {LS}}}}}_+$-perfect graphs. In Sect. 3, we characterize ${\mathrm {fs}}$-perfection in the family of graphs built from a minimally imperfect graph and one additional node. In Sect. 4 we prove the validity of the conjecture on ${\mathrm {fs}}$-perfect graphs. In order to ease the reading of this contribution, the proofs of results on the ${{{\mathrm{\text {LS}}}}}_+$ operator are presented in Sect. 5. Section 6 is devoted to the conclusions and some further results.

2 Further definitions and preliminary results

2.1 Graphs and the stable set polytope

Throughout this work, G stands for a simple graph with node set V(G) and edge set E(G). The complementary graph of G, denoted by $\overline{G}$, is such that $V(\overline{G}):=V(G)$ and, $E(\overline{G}):=\{uv: u \ne v, u,v\in V(G), uv \notin E(G)\}$. For any positive integer n, $K_n$, $C_n$ and $P_n$ denote the graphs with n nodes corresponding to a complete graph, a cycle and a path, respectively. We assume that in the cycle $C_{n}$ node i is adjacent to node $i+1$ for $i \in \{1,\ldots , n-1\}$ and n is adjacent to node 1.

Given $V'\subseteq V(G)$, we say that $G'$ is a subgraph of G induced by the nodes in $V'$ if $V(G')=V'$ and $E(G')=\{uv: uv\in E(G), \{u,v\}\subseteq V(G')\}$. When $V(G')$ is clear from the context, we say that $G'$ is a node induced subgraph of G and write $G'\subseteq G$. Given $U\subseteq V(G)$, we denote by $G-U$ the subgraph of G induced by the nodes in $V(G){\setminus }U$. For simplicity, we write $G-u$ instead of $G-\{u\}$. We say that $G_E$ is an edge subgraph of G if $V(G_E)=V(G)$ and $E(G_E)\subseteq E(G)$.

Given the graph G, the set $\Gamma _G(v)$ is the neighbourhood of node $v\in V(G)$ and $\delta _G(v)=|\Gamma _G(v)|$. The set $\Gamma _G[v]=\Gamma _G(v)\cup \{v\}$ is the closed neighbourhood of node v. When the graph is clear from the context, we simply write $\Gamma (v)$ or $\Gamma [v]$. If $G'\subseteq G$ and $v\in V(G)$, $G'\ominus v$ is the subgraph of G induced by the nodes in $V(G'){\setminus }\Gamma [v]$. We say that $G'\ominus v$ is obtained from $G'$ by destruction of $v\in V(G)$.

A stable set in G is a subset of mutually nonadjacent nodes in G and a clique is a subset of pairwise adjacent nodes in G. The cardinality of a stable set of maximum cardinality in G is denoted by $\alpha (G)$. The stable set polytope in G, ${{\mathrm{\text {STAB}}}}(G)$, is the convex hull of the characteristic vectors of stable sets in G. The support of a valid inequality of the stable set polytope of a graph G is the subgraph induced by the nodes with nonzero coefficient in the inequality. A full-support inequality has G as its support.

If $G'\subseteq G$, we may consider every point in ${{\mathrm{\text {STAB}}}}(G')$ as a point in ${{\mathrm{\text {STAB}}}}(G)$, although they do not belong to the same space (for the missing nodes, we take direct sums with the interval [0, 1], since originally ${{\mathrm{\text {STAB}}}}(G) \subseteq {{\mathrm{\text {STAB}}}}(G') \oplus [0,1]^{V(G) \setminus V(G')}$). Then, given any family of graphs $\mathcal {F}$ and a graph G, we denote by $\mathcal {F}(G)$ the relaxation of ${{\mathrm{\text {STAB}}}}(G)$ defined by

$$\begin{aligned} \mathcal {F}(G):=\bigcap \limits _{G'\subseteq G; G'\in \mathcal {F}} {{\mathrm{\text {STAB}}}}(G'). \end{aligned}$$

(1)

If ${{\mathrm{\text {FRAC}}}}$ denotes the family of complete graphs of size two, following the definition (1), the polyhedron ${{\mathrm{\text {FRAC}}}}(G)$ is called the edge relaxation. It is known that G is bipartite if and only if ${{\mathrm{\text {STAB}}}}(G)= {{\mathrm{\text {FRAC}}}}(G)$. Similarly, if ${{\mathrm{\text {CLIQUE}}}}$ denotes the family of complete graphs, ${{\mathrm{\text {CLIQUE}}}}(G)$ is the clique relaxation already mentioned and a graph is perfect if and only if ${{\mathrm{\text {STAB}}}}(G)={{\mathrm{\text {CLIQUE}}}}(G)$ [14]. Moreover, if ${{\mathrm{\text {OC}}}}$ denotes the family of odd cycles, as a consequence of results in [28] we have the following

Remark 5

If $G-v$ is bipartite for some $v\in V(G)$ then ${{\mathrm{\text {STAB}}}}(G)= {{\mathrm{\text {FRAC}}}}(G) \cap {{\mathrm{\text {OC}}}}(G)$.

In [33] Shepherd defined a graph G to be near-bipartite if $G\ominus v$ is bipartite for every $v\in V(G)$. We denote by ${{\mathrm{\text {NB}}}}$ the family of near-bipartite graphs. Since complete graphs and odd cycles are near-bipartite graphs, it is clear that

$$\begin{aligned} {{\mathrm{\text {NB}}}}(G)\subseteq {{\mathrm{\text {CLIQUE}}}}(G)\cap {{\mathrm{\text {OC}}}}(G). \end{aligned}$$

2.2 Minimally imperfect, near-perfect and fs-perfect graphs

Minimally imperfect graphs are those graphs that are not perfect, but after deleting any node they become perfect. The Strong Perfect Graph Theorem [13] (also see [11]; and see [12] for the related recognition problem) states that the only minimally imperfect graphs are the odd cycles and their complements.

Given a graph G it is known that the full-rank constraint

$$\begin{aligned} \sum _{u\in V} x_u\le \alpha (G) \end{aligned}$$

is always valid for ${{\mathrm{\text {STAB}}}}(G)$. A graph is near-perfect if its stable set polytope is defined only by non-negativity constraints, clique constraints and the full-rank constraint [32]. Due to the results of Chvátal [14], near-perfect graphs define a superclass of perfect graphs and due to the results in [30], minimally imperfect graphs are also near-perfect. Moreover, every node induced subgraph of a near-perfect graph is near-perfect [32]. In addition, Shepherd [32] conjectured that near-perfect graphs could be characterized in terms of certain combinatorial parameters and established that the validity of his conjecture follows from the Strong Perfect Graph (then Conjecture, now) Theorem. Therefore,

Theorem 6

([13, 32]) A graph G is near-perfect if and only if, for every $G'\subseteq G$ minimally imperfect, the following two properties hold:

• (1) $\alpha (G')=\alpha (G)$;

• (2) for all $v\in V(G)$, $\alpha (G'\ominus v)=\alpha (G)-1$.

As a generalization of near-perfect graphs, we consider the family of ${\mathrm {fs}}$-perfect (full-support perfect) graphs. A graph is ${\mathrm {fs}}$-perfect if its stable set polytope is defined only by non-negativity constraints, clique constraints and at most one full-support inequality. Then, every node induced subgraph of an ${\mathrm {fs}}$-perfect graph is ${\mathrm {fs}}$-perfect. We say that a graph is properly ${\mathrm {fs}}$-perfect if it is an imperfect ${\mathrm {fs}}$-perfect graph. Clearly, near-perfect graphs are ${\mathrm {fs}}$-perfect, but we will see that ${\mathrm {fs}}$-perfect graphs define a strict superclass of near-perfect graphs.

2.3 The ${{{\mathrm{\text {LS}}}}}_+$ operator

In this section, we present a definition of the ${{{\mathrm{\text {LS}}}}}_+$-operator [28] and some of its well-known properties when it is applied to relaxations of the stable set polytope of a graph. In order to do so, we need some more notation and definitions.

We denote by ${\mathbf e}_0, {\mathbf e}_1, \dots , {\mathbf e}_n$ the vectors of the canonical basis of ${\mathbb {R}}^{n+1}$ where the first coordinate is indexed zero. Given a convex set K in $[0,1]^n$,

$$\begin{aligned} {{\mathrm{cone}}}(K) := \left\{ \left( \begin{array}{c} x_0\\ x \end{array} \right) \in {\mathbb {R}}^{n+1}: x=x_0 y ; y\in K; x_0 \ge 0 \right\} . \end{aligned}$$

Let ${\mathbb {S}}^{n}$ be the space of $n\times n$ symmetric matrices with real entries. If $Y\in {\mathbb {S}}^n$, $\text {diag}(Y)$ denotes the vector whose ith entry is $Y_{ii}$, for every $i \in \{1,\ldots ,n\}$. Let

$$\begin{aligned} M(K) := \left\{ Y \in {\mathbb {S}}^{n+1}: \right.&Y{\mathbf e}_0 = \text {diag}(Y),\\&Y{\mathbf e}_i \in {{\mathrm{cone}}}(K), \\&\left. Y ({\mathbf e}_0 - {\mathbf e}_i) \in {{\mathrm{cone}}}(K), \forall i \in \{1,\dots ,n \} \right\} . \end{aligned}$$

Projecting this polyhedral lifting back to the space ${\mathbb {R}}^n$ results in

$$\begin{aligned} {{\mathrm{\text {LS}}}}(K) := \left\{ x \in [0,1]^n : \left( \begin{array}{c} 1\\ x \end{array} \right) = Y {\mathbf e}_0, \text{ for } \text{ some } Y \in M(K)\right\} . \end{aligned}$$

Clearly, ${{\mathrm{\text {LS}}}}(K)$ is a relaxation of the convex hull of integer solutions in K, i.e., ${{\mathrm{conv}}}(K\cap \{0,1\}^n)$.

Let ${\mathbb {S}}_+^{n}$ be the space of $n\times n$ symmetric positive semidefinite (PSD) matrices with real entries. Then

$$\begin{aligned} M_+(K) := M(K) \cap {\mathbb {S}}_+^{n+1} \end{aligned}$$

yields the tighter relaxation

$$\begin{aligned} {{{\mathrm{\text {LS}}}}}_+(K) := \left\{ x \in [0,1]^{n} : \left( \begin{array}{c} 1\\ x \end{array} \right) = Y {\mathbf e}_0, \text{ for } \text{ some } Y \in M_+(K)\right\} . \end{aligned}$$

If we let ${{\mathrm{\text {LS}}}}^0(K):=K$, then the successive applications of the ${{\mathrm{\text {LS}}}}$ operator yield ${{\mathrm{\text {LS}}}}^k(K)={{\mathrm{\text {LS}}}}({{\mathrm{\text {LS}}}}^{k-1}(K))$ for every $k\ge 1$. Similarly for the ${{{\mathrm{\text {LS}}}}}_+$ operator. Lovász and Schrijver proved that ${{\mathrm{\text {LS}}}}^n(K)={{{\mathrm{\text {LS}}}}}_+^n(K)={{\mathrm{conv}}}(K\cap \{0,1\}^n)$.

In this paper, we focus on the behaviour of the ${{{\mathrm{\text {LS}}}}}_+$ operator on the edge relaxation of the stable set polytope. In order to simplify the notation we write ${{{\mathrm{\text {LS}}}}}_+(G)$ instead of ${{{\mathrm{\text {LS}}}}}_+({{\mathrm{\text {FRAC}}}}(G))$ and similarly for the successive iterations of it. It is known [28] that, for every graph G,

$$\begin{aligned} {{\mathrm{\text {STAB}}}}(G) \subseteq {{{\mathrm{\text {LS}}}}}_+(G)\subseteq \text {TH}(G)\subseteq {{\mathrm{\text {CLIQUE}}}}(G) \end{aligned}$$

and

$$\begin{aligned} {{\mathrm{\text {STAB}}}}(G) \subseteq {{{\mathrm{\text {LS}}}}}_+(G)\subseteq {{\mathrm{\text {NB}}}}(G). \end{aligned}$$

2.4 ${{{\mathrm{\text {LS}}}}}_+$-perfect graphs

Recall that a graph G is ${{{\mathrm{\text {LS}}}}}_+$-perfect if ${{{\mathrm{\text {LS}}}}}_+(G) = {{\mathrm{\text {STAB}}}}(G)$. A graph that is not ${{{\mathrm{\text {LS}}}}}_+$-perfect is called ${{{\mathrm{\text {LS}}}}}_+$-imperfect.

Using the results in [16] and [26] we know that all imperfect graphs with at most 6 nodes are ${{{\mathrm{\text {LS}}}}}_+$-perfect, except for the two properly near-perfect graphs depicted in Fig. 1, denoted by $G_{LT}$ and $G_{EMN}$, respectively. These graphs prominently figure into our current work as the building blocks of an interesting family of graphs.

Fig. 1

The graphs $G_{LT}$ and $G_{EMN}$

From the results in [28], it can be proved that every subgraph of an ${{{\mathrm{\text {LS}}}}}_+$-perfect graph is also ${{{\mathrm{\text {LS}}}}}_+$-perfect. Moreover, every graph for which ${{\mathrm{\text {STAB}}}}(G)={{\mathrm{\text {NB}}}}(G)$ is ${{{\mathrm{\text {LS}}}}}_+$-perfect. In particular, perfect and near-bipartite graphs are ${{{\mathrm{\text {LS}}}}}_+$-perfect. Recall that in Conjecture 3 we wonder whether the only ${{{\mathrm{\text {LS}}}}}_+$-perfect graphs are those graphs G for which ${{\mathrm{\text {STAB}}}}(G)={{\mathrm{\text {NB}}}}(G)$. Obviously, G is ${{{\mathrm{\text {LS}}}}}_+$-perfect if and only if every facet defining inequality of ${{\mathrm{\text {STAB}}}}(G)$ is valid for ${{{\mathrm{\text {LS}}}}}_+(G)$. In this context, we have Lemma 1.5 in [28] that can be rewritten in the following way:

Theorem 7

Let $ax\le \beta$ be a full-support valid inequality for ${{\mathrm{\text {STAB}}}}(G)$. If, for every $v\in V(G)$, $\sum _{w\in V(G-v)} ax\le \beta - a_v$ is valid for ${{\mathrm{\text {FRAC}}}}(G\ominus v)$ then $ax\le \beta$ is valid for ${{{\mathrm{\text {LS}}}}}_+(G)$.

In [6] we proved that the converse of the previous result is not true. However, it is plausible that the converse holds when the full-support valid inequality is a facet defining inequality of ${{\mathrm{\text {STAB}}}}(G)$. Actually, the latter assertion would be a consequence of the validity of Conjecture 3. Thus, we present an equivalent formulation of it in the following.

Conjecture 8

If a graph is ${{{\mathrm{\text {LS}}}}}_+$-perfect and its stable set polytope has a full-support facet defining inequality, then the graph is near-bipartite.

2.5 Graph operations

In this section, we present some properties of four graph operations that will be used throughout this paper. Firstly, let us recall the complete join of graphs. Given two graphs $G_1$ and $G_2$ such that $V(G_1)\cap V(G_2)=\emptyset$, we say that a graph G is obtained after the complete join of $G_1$ and $G_2$, denoted $G=G_1 \vee G_2$, if $V(G)=V(G_1) \cup V(G_2)$ and $E(G)= E(G_1) \cup E(G_2) \cup \{vw: v\in V(G_1)\text { and }w\in V(G_2)\}$. A simple example of a join is the n-wheel $W_n$, for $n\ge 2$ which is the complete join of the trivial graph with one node and the n-cycle.

It is known that every facet defining inequality of ${{\mathrm{STAB}}}(G_1 \vee G_2)$ can be obtained by the cartesian product of facets of ${{\mathrm{STAB}}}(G_1)$ and ${{\mathrm{STAB}}}(G_2)$. Hence, odd wheels are ${\mathrm {fs}}$-perfect but not near-perfect graphs. Moreover, it is easy to see

Remark 9

The complete join of two graphs is properly ${\mathrm {fs}}$-perfect if and only if one of them is a complete graph and the other one is a properly ${\mathrm {fs}}$-perfect graph.

Also, it is known that

Remark 10

The complete join of two graphs is ${{{\mathrm{\text {LS}}}}}_+$-perfect if and only if both of them are ${{{\mathrm{\text {LS}}}}}_+$-perfect graphs.

Now, let us recall the graph operation, odd-subdivision of an edge [35]. Given a graph $G=(V,E)$ and $e\in E$, we say that the graph $G'$ is obtained from G after an odd-subdivision of the edge e if it is replaced in G by a path of odd length. Next, we consider the k-stretching of a node which is a generalization of the type (i) stretching operation defined in [26]. Let v be a node of G with neighborhood $\Gamma (v)$ and let $A_1$ and $A_2$ be nonempty subsets of $\Gamma (v)$ such that $A_1 \cup A_2 = \Gamma (v)$, and $A_1\cap A_2$ is a clique of size k. A k -stretching of a node v is obtained as follows: remove v, introduce three nodes instead, called $v_1$, $v_2$ and u, and add an edge between $v_i$ and every node in $\{u\} \cup A_i$ for $i \in \{1, 2\}$. Figure 2 illustrates the case $k=1$.

Fig. 2

A 1-stretching operation on node v

The type (i) stretching operation presented in [26] corresponds to the case $k=0$.

We also consider another graph operation defined in [4]. Given a graph G with nodes $\{1, \dots ,n\}$ and a clique $K = \{v_1,\dots , v_s\}$ in G (not necessarily maximal), the clique subdivision of the edge $v_1 v_2$ in K is defined as follows: delete the edge $v_1 v_2$ from G, add the nodes $v_{n+1}$ and $v_{n+2}$ together with the edges $v_1 v_{n+1}$, $v_{n+1} v_{n+2}$, $v_{n+2} v_2$ and $v_{n+i} v_j$ for $i \in \{1, 2\}$ and $j \in \{3,\dots , s\}$. Figure 3 illustrates the clique subdivision of the edge $v_1 v_2$ in the clique $K = \{v_1, v_2, v_6\}$.

Fig. 3

The graph $G'$ is obtained from G after the clique subdivision of edge $v_1v_2$

Notice that if the clique is an edge this operation reduces to the odd-subdivision of it.

3 ${\mathrm {fs}}$-perfection on graphs in ${\mathcal {F}}^k$

In order to prove Conjecture 8 on ${\mathrm {fs}}$-perfect graphs, we first consider a minimal structure that a graph must have in order to be properly ${\mathrm {fs}}$-perfect and ${{{\mathrm{\text {LS}}}}}_+$-imperfect. This leads us to define ${\mathcal {F}}^k$ for every $k\ge 2$ as the family of graphs having node set $\{0,1,\dots ,2k+1\}$ and such that $G-0$ is a minimally imperfect graph with $1\le \delta _G(0)\le 2k$. Let us consider necessary conditions for a graph in ${\mathcal {F}}^k$ to be ${\mathrm {fs}}$-perfect.

Theorem 11

[29] Let $G\in {\mathcal {F}}^k$ be an ${\mathrm {fs}}$-perfect graph. Then, the following conditions hold:

• (1) $\alpha (G)=\alpha (G-0)$;

• (2) $1\le \alpha (G\ominus 0) \le \alpha (G)-1$;

• (3) the full-support facet defining inequality of ${{\mathrm{\text {STAB}}}}(G)$ is the inequality

  $$\begin{aligned} \left( \alpha (G)-\alpha (G \ominus 0)\right) x_0+\sum _{i=1}^{2k+1} x_i\le \alpha (G). \end{aligned}$$

Proof

Let

$$\begin{aligned} \sum _{i=0}^{2k+1}a_i x_i\le \beta \end{aligned}$$

(2)

be the full-support facet defining inequality of ${{\mathrm{STAB}}}(G)$. We may assume that all coefficients $a_i$, $i \in \{0,\dots ,2k+1\}$ are positive integers. Clearly,

$$\begin{aligned} {{\mathrm{STAB}}}(G-0)=\left\{ x\in {{\mathrm{CLIQUE}}}(G-0): \sum _{i=1}^{2k+1} a_i x_i\le \beta \right\} . \end{aligned}$$

Since $G-0$ is a minimally imperfect graph, the inequality $\sum _{i=1}^{2k+1} a_i x_i\le \beta$ is a positive multiple of its rank constraint, i.e., there exists a positive integer p such that $a_i= p$ for $i \in \{1,\dots , 2k+1\}$ and $\beta = p \ \alpha (G-0).$ Therefore, (2) has the form

$$\begin{aligned} a_0 x_0+ p\sum _{i=1}^{2k+1} x_i\le p \ \alpha (G-0). \end{aligned}$$

(3)

Observe that there is at least one root $\tilde{x}$ of (3) such that $\tilde{x}_0=1$. Clearly, $\tilde{x}$ is the incidence vector of a stable set S of G such that $S-\{0\}$ is a maximum cardinality stable set of $G\ominus 0$. Then,

$$\begin{aligned} a_0= p \ \left( \alpha (G-0)- \alpha (G\ominus 0)\right) . \end{aligned}$$

Since $a_0\ge 1$, we have $\alpha (G\ominus 0)\le \alpha (G-0)-1$. Moreover, since $\delta _G(0)\le 2k$, we have $\alpha (G\ominus 0)\ge 1$. Therefore, the inequality (3) becomes

$$\begin{aligned} (\alpha (G-0)- \alpha (G\ominus 0)) x_0+ \sum _{i=1}^{2k+1} x_i\le \alpha (G-0). \end{aligned}$$

(4)

To complete the proof, we only need to show that $\alpha (G)=\alpha (G-0)$. Let $\bar{x}$ be the incidence vector of a maximum cardinality stable set in G, then

$$\begin{aligned} \alpha (G)=\bar{x}_0+\sum _{i=1}^{2k+1}\bar{x}_i. \end{aligned}$$

(5)

Moreover, since $\alpha (G-0)- \alpha (G\ominus 0)\ge 1$ and $\bar{x}$ satisfies (4) we have

$$\begin{aligned} \alpha (G)=\bar{x}_0+\sum _{i=1}^{2k+1}\bar{x}_i\le (\alpha (G-0)- \alpha (G\ominus 0)) \bar{x}_0+ \sum _{i=1}^{2k+1} \bar{x}_i\le \alpha (G-0). \end{aligned}$$

We have that $\alpha (G)\le \alpha (G-0)$, implying $\alpha (G)=\alpha (G-0)$.$\square$

As a first consequence of the previous theorem we have:

Corollary 12

Let $G\in {\mathcal {F}}^k$ be such that $\alpha (G)=2$. Then, G is ${\mathrm {fs}}$-perfect if and only if $G-0=\overline{C_{2k+1}}$ (the complementary graph of $C_{2k+1}$) and G is near-perfect.

Proof

Assume that G is ${\mathrm {fs}}$-perfect. By the previous theorem, $\alpha (G-0)= \alpha (G)=2$ and then $G-0=\overline{C_{2k+1}}$. Moreover, $1\le \alpha (G\ominus 0)\le \alpha (G)-1=1$ and $a_0=1$. Thus, G is near-perfect. The converse follows from the definition of ${\mathrm {fs}}$-perfect graphs.$\square$

For $k\ge 2$, let $H^k$ denote the graph in ${\mathcal {F}}^k$ having $\alpha (H^k)=2$ and $\delta _{H^k}(0)=2k$. Using Theorem 6 it is easy to check that $H^k$ is near-perfect. Using Corollary 12, we have the following result:

Corollary 13

Let $G\in {\mathcal {F}}^k$ be such that $\alpha (G)=2$. Then, G is ${\mathrm {fs}}$-perfect if and only if G is a near-perfect edge subgraph of $H^k$.

Let us now study the structure of ${\mathrm {fs}}$-perfect graphs G in ${\mathcal {F}}^k$ with stability number at least 3. By Theorem 11, $\alpha (G-0)=\alpha (G)\ge 3$ and $G-0=C_{2k+1}$ with $k\ge 3$. Recall that in the cycle $C_{2k+1}$ node i is adjacent to node $i+1$ for $i \in \{1,\ldots , 2k\}$ and $2k+1$ is adjacent to node 1. Clearly, if $\delta (0)\le 2$ and $0v \in E(G)$ then $G-v$ is bipartite and, by Remark 5, G is not ${\mathrm {fs}}$-perfect.

From now on, $3\le s=\delta (0)\le 2k$ and $\Gamma (0)=\{v_1,\ldots ,v_s\}$ such that $1\le v_1<\ldots <v_{s}\le 2k+1$. Observe that for every $i \in \{1,\ldots ,s-1\}$, the nodes in $\{w\in V(G-0): v_i\le w \le v_{i+1}\}$ together with node 0 form a chordless cycle $D_i$ in G. Also, $D_s$ in G is the chordless cycle induced by the nodes in $\{w\in V(G-0): v_s\le w \le 2k+1 \text { or } 1\le w \le v_1 \}$ and node 0. We refer to these cycles as central cycles of G. Sometimes, we refer to central cycles of length k as k-central cycles. It is easy to see, using parity arguments, that every $G\in {\mathcal {F}}^k$ has an odd number of odd central cycles. If G has only one odd central cycle, say $D_1$, then $G-v_1$ is bipartite and, by Remark 5, G is not ${\mathrm {fs}}$-perfect.

We summarize the previous ideas in the following result:

Lemma 14

Let $G\in {\mathcal {F}}^k$ be a ${\mathrm {fs}}$-perfect graph with $\alpha (G)\ge 3$. Then, $k\ge 3$, $G-0=C_{2k+1}$ and G has at least three odd central cycles.

According to the lemma above, we may focus on the structural properties of graphs in ${\mathcal {F}}^k$ with at least three odd central cycles. Firstly, we have:

Lemma 15

Let $G\in {\mathcal {F}}^k$ with $k\ge 3$ be such that $G-0=C_{2k+1}$ and G has at least three odd central cycles. Then, G can be obtained after some odd subdivisions of edges in a graph $G'\in {\mathcal {F}}^p$ for some $2\le p<k$ with $\delta _{G'}(0)=\delta _{G}(0)$. Moreover,

• (1) if every central cycle of G is odd, $G'$ has one central cycle of length 5 and $2(p-1)$ central cycles of length 3;

• (2) if G has an even central cycle, every central cycle of $G'$ has length 3 or 4.

Proof

Let $\delta _{G}(0)=s$ with $s\ge 3$.

• (1) If every central cycle of G is odd then s is odd and G has a central cycle with length at least 5. Let $p=\frac{s+1}{2}$ and $G'\in {\mathcal {F}}^p$ with $\delta _{G'}(0)=s$ such that 0 is adjacent to all nodes in $C_{2p+1}$ except to two nodes, e.g., nodes s and $s+1$. Clearly, $G'$ has one central cycle of length five, and $s-1=2(p-1)$ central cycles of length three. Hence G is obtained after some odd subdivisions of edges of $G'$.

• (2) If G has $r\ge 1$ even central cycles then $s+r$ is odd. Let $D_i$ with $i \in \{1,\ldots , s \}$ be the central cycles of G. Let $p= \frac{s+r-1}{2}$ and $G'\in {\mathcal {F}}^p$ such that $\delta _{G'}(0)=s$ and for $i \in \{1,\ldots , s\}$ the central cycle $D'_i$ in $G'$ is:

  • (a) a 3-cycle if $D_i$ is odd,

  • (b) a 4-cycle If $D_i$ is even.

  It is straightforward to check that G is obtained from $G'$ after some odd subdivisions of edges.$\square$

In addition, we have

Lemma 16

Let $G\in {\mathcal {F}}^k$ with $k\ge 3$ be such that $G-0=C_{2k+1}$ and $\delta _G(0)\ge 3$. Let t(G) be the number of 3-central cycles and r(G) the number of 4-central cycles in G.

• (1) if G has three consecutive 3-central cycles then G can be obtained after the clique subdivision of an edge in a graph $G'\in {\mathcal {F}}^{k-1}$ with $t(G')=t(G)-2$ and $\delta _{G'}(0)=\delta _G(0)-2$;

• (2) if $r(G)\ge 2$ then G can be obtained after the 1-stretching operation on a node in a graph $G'\in {\mathcal {F}}^{k-1}$ with $r(G')=r(G)-1$ and $\delta _{G'}(0)=\delta _{G}(0)-1$.

Proof

• (1) By the hypothesis, we may consider that $\{2k-1,2k,2k+1,1\}\subseteq \Gamma (0)$. Let $G'\in {\mathcal {F}}^{k-1}$ be a graph having $\Gamma _{G'}(0)=\Gamma (0)\setminus \{2k,2k+1\}$. Clearly, $G'$ has $t(G)-2$ 3-central cycles and $\delta _{G'}(0)=\delta _{G}(0)-2$. Moreover, it is easy to see that G is the clique subdivision of the edge in $G'$ having endpoints $\{1,2k-1\}$.

• (2) Since there is a 4-central cycle, without loss of generality, we may assume that the nodes in $\{0,1,2k, 2k+1\}$ induce a 4-central cycle in G. Consider $G'\in F^{k-1}$ such that $\Gamma _{G'}(0)=\Gamma _G(0)\setminus \{2k\}$, then G is a 1-stretching of $G'$ performed at node 1 and where the new nodes are 2k and $2k+1$. Clearly, $r(G')=r(G)-1$ and $\delta _{G'}(0)=\delta _{G}(0)-1$.$\square$

Utilizing the previous lemmas we obtain the following result.

Theorem 17

Let $G\in {\mathcal {F}}^k$ with $k\ge 3$ and suppose G has at least three odd central cycles. Then, G can be obtained from $G_{LT}$ or $G_{EMN}$ after successively applying odd-subdivision of an edge, 1-stretching of a node and clique-subdivision of an edge operations.

Proof

Using Lemma 15, by successively performing the odd subdivision of an edge operation, we may restrict ourselves to consider the following cases:

• (a) G has one 5-central cycle and $2(k-1)$ 3-central cycles.

• (b) G has at least one even central cycle and every central cycle has length 3 or 4.

Consider r(G), the number of 4-cycles in G. If $r(G)=0$ then G is a graph described in case (a). Since $k\ge 3$, we have $2(k-1)\ge 4$, and by Lemma 16 (1), we can conclude that G is obtained from $G_{LT}$ after successive clique-subdivisions of edges. For graphs in case (b), we have that $r(G)\ge 1$ and then by Lemma 15 (2) we have that $2k=r(G)+\delta (G)-1$. If $r(G)=1$ and $\delta (G)$ is even, since $k\ge 3$ it follows that G has $t(G)=\delta (G)-1\ge 5$ number of 3-cycles. Using Lemma 16 (1) it is not hard to see that G can be obtained from $G_{EMN}$ by successive clique subdivisions of edges. If $r(G)\ge 2$, Lemma 16 (2) implies that G can be obtained by successive 1-stretching of nodes from a graph $G'\in {\mathcal {F}}^{k'}$ with $r(G')=1$ and $2k'=\delta (G')$. If $2k'=4$, then $G'=G_{EMN}$; otherwise, we can refer to the previous case and the proof is complete.$\square$

4 The conjecture on ${\mathrm {fs}}$-perfect graphs

In this section, we prove the validity of Conjecture 8 on the family of ${\mathrm {fs}}$-perfect graphs. We start by proving it on graphs in the family ${\mathcal {F}}^k$ with $k\ge 2$. Recall that when $G\in {\mathcal {F}}^k$ is a ${\mathrm {fs}}$-perfect graph with $\alpha (G)=2$, Corollary 13 states that G is a near-perfect edge subgraph of $H^k$. Observe that $H^2=G_{EMN}$ and then, due to the results in [16], $H^k$ is ${{{\mathrm{\text {LS}}}}}_+$-imperfect when $k=2$.

Next, we prove the imperfection property for the whole family of graphs $H^k$.

Theorem 18

For $k\ge 2$, the graph $H^k$ is ${{{\mathrm{\text {LS}}}}}_+$-imperfect.

In order to ease the reading of this paper we postpone the proof of Theorem 18 to Sect. 5. Regarding the behaviour of the ${{{\mathrm{\text {LS}}}}}_+$ operator on edge subgraphs, we have the following result:

Lemma 19

Let $G_E$ be an edge subgraph of G and $a x \le \beta$ be a valid inequality for ${{\mathrm{\text {STAB}}}}(G_E)$. Then, if $a x \le \beta$ is not valid for ${{\mathrm{\text {LS}}}}^r_+(G)$, then ${{\mathrm{\text {STAB}}}}(G_E)\ne {{\mathrm{\text {LS}}}}^r_+(G_E)$.

Proof

Clearly, by definition ${{\mathrm{\text {LS}}}}^r_+(G)\subseteq {{\mathrm{\text {LS}}}}^r_+(G_E)$. Thus, if there exists $\hat{x}\in {{\mathrm{\text {LS}}}}^r_+(G)$ such that $a \hat{x} > \beta$ then $a x\le \beta$ is not valid for ${{\mathrm{\text {LS}}}}^r_+(G_E)$. Moreover, by hypothesis, $a x\le \beta$ is valid for ${{\mathrm{\text {STAB}}}}(G_E)$ and the result follows.$\square$

As a consequence of the above, we have:

Theorem 20

Let $G \in \mathcal {F}^k$ be an ${\mathrm {fs}}$-perfect graph with $\alpha (G)=2$. Then, G is ${{{\mathrm{\text {LS}}}}}_+$-imperfect.

Proof

By Corollary 13 we know that G is a near-perfect edge subgraph of $H^k$. Theorem 18 states that $H^k$ is ${{{\mathrm{\text {LS}}}}}_+$-imperfect; thus, the full rank constraint is not valid for ${{{\mathrm{\text {LS}}}}}_+(H^k)$. Since $\alpha (H^k)=\alpha (G)=2$, the full rank constraint is not valid for ${{{\mathrm{\text {LS}}}}}_+(G)$ and G is ${{{\mathrm{\text {LS}}}}}_+$-imperfect.$\square$

Let us consider the ${\mathrm {fs}}$-perfect graphs G in ${\mathcal {F}}^k$ with $\alpha (G)\ge 3$. Due to the structural characterization in Theorem 17, we are interested in the behavior of the ${{{\mathrm{\text {LS}}}}}_+$-operator under the odd subdivision of an edge, k-stretching of a node and clique subdivision of an edge operations. In this context, a related earlier result is:

Theorem 21

([26]) Let G be a graph and $r \ge 1$ such that ${{{\mathrm{\text {LS}}}}}_+^r(G) \ne {{\mathrm{\text {STAB}}}}(G)$. Further assume that $\tilde{G}$ is obtained from G by using the odd subdivision operation on one of its edges. Then, ${{{\mathrm{\text {LS}}}}}_+^r(\tilde{G}) \ne {{\mathrm{\text {STAB}}}}(\tilde{G})$.

Concerning the remaining operations, we present the following results whose proofs are included in Sect. 5 for the sake of clarity.

Theorem 22

Let G be a graph and $r \ge 1$ such that ${{{\mathrm{\text {LS}}}}}_+^r(G) \ne {{\mathrm{\text {STAB}}}}(G)$. Further assume that $\tilde{G}$ is obtained from G by using the k-stretching operation on one of its nodes. Then, ${{{\mathrm{\text {LS}}}}}_+^r(\tilde{G}) \ne {{\mathrm{\text {STAB}}}}(\tilde{G})$.

Theorem 23

Let G be a graph and $r \ge 1$ such that ${{{\mathrm{\text {LS}}}}}_+^r(G) \ne {{\mathrm{\text {STAB}}}}(G)$. Further assume that $\tilde{G}$ is obtained from G by using the clique subdivision operation on one of its edges. Then, ${{{\mathrm{\text {LS}}}}}_+^r(\tilde{G}) \ne {{\mathrm{\text {STAB}}}}(\tilde{G})$.

In summary, we can conclude that the odd-subdivision of an edge, the 1-stretching of a node and the clique-subdivision of an edge are operations that preserve ${{{\mathrm{\text {LS}}}}}_+$-imperfection. Then, the behavior of these operations under the ${{{\mathrm{\text {LS}}}}}_+$ operator together with the fact that graphs $G_{LT}$ and $G_{EMN}$ are ${{{\mathrm{\text {LS}}}}}_+$-imperfect, Lemma 14 and Theorem 17 allow us to deduce:

Theorem 24

Let $G\in {\mathcal {F}}^k$ be an ${\mathrm {fs}}$-perfect graph with $\alpha (G)\ge 3$. Then, G is ${{{\mathrm{\text {LS}}}}}_+$-imperfect.

Finally, we are able to present the main result of this contribution.

Theorem 25

Let G be a properly ${\mathrm {fs}}$-perfect graph which is also ${{{\mathrm{\text {LS}}}}}_+$-perfect. Then, G is the complete join of a complete graph (possibly empty) and a minimally imperfect graph.

Proof

Since G is a properly ${\mathrm {fs}}$-perfect graph, G has a $(2k+1)$-minimally imperfect node induced subgraph $G'$. If $G'=G$ the theorem follows. Otherwise, let $v\in V(G)\setminus V(G')$ and let $G_v$ be the subgraph of G induced by $\{v\}\cup V(G')$. Clearly, $G_v$ is properly ${\mathrm {fs}}$-perfect as well as ${{{\mathrm{\text {LS}}}}}_+$-perfect. Then, by Theorem 20 and Theorem 24, $G_v\notin {\mathcal {F}}^k$. So, $\delta _{G_v}(v)=2k+1$ and $G_v=\{v\}\vee G'$. Therefore, if $G''$ is the subgraph of G induced by $V(G)-V(G')$, $G=G' \vee G''$. By Remark 9, $G''$ is a complete graph and by Remark the result follows.$\square$

Since complete joins of complete graphs and minimally imperfect graphs are near-bipartite, they satisfy ${\mathrm {NB}}(G)={{\mathrm{STAB}}}(G)$. Therefore, based on the results obtained so far, we can conclude that Conjecture 8 holds for ${\mathrm {fs}}$-perfect graphs.

5 Results concerning the ${{{\mathrm{\text {LS}}}}}_+$-operator

In this section we include the proofs of some results on the ${{{\mathrm{\text {LS}}}}}_+$-operator that were stated without proof in the previous sections.

5.1 The ${{{\mathrm{\text {LS}}}}}_+$-imperfection of the graph $H^k$

Recall that $V(H^k)=\{0,1,\ldots ,2k+1\}$, $H^k-0=\overline{C_{2k+1}}$ and $\delta (0)=2k$. Without loss of generality, we may assume that the node $2k+1$ in $H^k$ is the only one not connected with node 0. Let us introduce the point $x(k,\gamma ):=\frac{1}{2k+2+\gamma }(2,2,\dots ,2,4)^{\top } \in {\mathbb {R}}^{2k+2}$ where for $i \in \{1,\ldots , 2k+2\}$, the ith component of $x(k,\gamma )$ corresponds to the node $i-1$ in $H^k$. In what follows, we show that $x(k,\gamma )\in {{{\mathrm{\text {LS}}}}}_+(H^k)\setminus {{\mathrm{\text {STAB}}}}(H^k)$ for some $\gamma \in (0,1)$ thus proving Theorem 18. We first consider $\beta _k = \frac{1}{2k+2}$, $\gamma \in (0,1)$ and the $(2k+3)\times (2k+3)$ matrix given by

Lemma 26

For $k\ge 3$, there exists $\gamma \in (0,1)$ such that $Y(k,\gamma )$ is PSD.

Proof

Let us denote by $\tilde{Y}(k)$ the $(2k+2)\times (2k+2)$ submatrix of $Y(k,\gamma )$ obtained after deleting the first row and column. Also consider $\hat{Y}(k)$, the Schur Complement of the (1, 1) entry of $\tilde{Y}(k)$, then

Claim 27

For every $k \ge 2$, $\tilde{Y}(k)$ is positive definite.

Proof

Let us first show that $\hat{Y}(k)$ is positive definite. For this purpose, we only need to verify that every leading principal minor of $\hat{Y}(k)$ is positive.

Let us define $A_0(k):=1$, $B_0(k):=2$ and for $\ell \ge 1$,

where the matrix in the definition is $2\ell \times 2\ell$ and

where the matrix in the definition is $(2\ell +1)\times (2\ell +1)$. Using the determinant expansion on $A_{\ell }(k)$ and $B_{\ell }(k)$ we have that for every $\ell \ge 1$,

$$\begin{aligned} A_{\ell }(k)= & {} 2 B_{\ell -1}(k) -(1-\beta _k)^2 A_{\ell -1}(k),\\ B_{\ell }(k)= & {} 2 A_{\ell }(k) -(1+\beta _k)^2 B_{\ell -1}(k), \end{aligned}$$

and

$$\begin{aligned} \det \left( \hat{Y}(k)\right)= & {} 2 \left[ A_k(k) -(1+\beta _k)^2 B_{k-1}(k) + (1-\beta _k)^k (1+\beta _k)^{k+1}\right] \nonumber \\= & {} 2\left[ B_k(k) - A_k (k)+ (1-\beta _k)^k (1+\beta _k)^{k+1}\right] . \end{aligned}$$

(6)

Using these recursive formulas, we find that for every $\ell \ge 1$,

$$\begin{aligned} A_{\ell }(k)= & {} \left( 2\ell +1-\beta _k\right) (1-\beta _k)^{\ell -1} (1+\beta _k)^{\ell }, \end{aligned}$$

(7)

$$\begin{aligned} B_{\ell }(k)= & {} \left( 2\ell +2\right) (1-\beta _k)^{\ell } (1+\beta _k)^{\ell }. \end{aligned}$$

(8)

Note that $A_{\ell }(k)$ and $B_{\ell }(k)$ are positive for every $\ell$ and every k. Moreover, every leading principal minor of $\hat{Y}(k)$, except itself, is either $A_{\ell }(k)$ or $B_{\ell }(k)$ for some $\ell$. Using (6), (7) and (8) we compute

$$\begin{aligned} \det \left( \hat{Y}(k)\right) = 2 \left[ 2-(2k+1)\beta _k-\beta _k^2\right] (1-\beta _k)^{k-1} (1+\beta _k)^{k} \end{aligned}$$

(9)

which is indeed positive. Since we verified that every principle minor of $\hat{Y}(k)$ is positive, we deduce that $\hat{Y}(k)$ is positive definite. Finally, after applying the Schur Complement Lemma we have that $\tilde{Y}(k)$ is positive definite.$\square$

Using this claim we have:

Claim 28

Let u be the (unique) vector such that

$$\begin{aligned} \tilde{Y}(k) u = 2 (\mathbf {1}+ {\mathbf e}_{2k+2}). \end{aligned}$$

(10)

Then $Y(k,\gamma )$ is PSD if and only if $\gamma \ge 1-\beta _k u_{2k+2}$.

Proof

Using the Schur Complement Lemma for $\tilde{Y}(k)$ we have that $Y(k,\gamma )$ is PSD if and only if

$$\begin{aligned} \tilde{Y}(k) - \frac{4}{2k+2+\gamma } (\mathbf {1}+ {\mathbf e}_{2k+2})(\mathbf {1}+ {\mathbf e}_{2k+2})^{\top } \text { is PSD}. \end{aligned}$$

Using the automorphism $\left[ \tilde{Y}(k)\right] ^{-1/2} \cdot \left[ \tilde{Y}(k)\right] ^{-1/2}$ of the PSD cone, the latter is true if and only if the following matrix

$$\begin{aligned} I - \frac{4}{2k+2+\gamma } \left[ \tilde{Y}(k)\right] ^{-1/2} (\mathbf {1}+ {\mathbf e}_{2k+2})(\mathbf {1}+ {\mathbf e}_{2k+2})^{\top } \left[ \tilde{Y}(k)\right] ^{-1/2} \end{aligned}$$

(11)

is PSD. Since

$$\begin{aligned} \frac{4}{2k+2+\gamma } \left[ \tilde{Y}(k)\right] ^{-1/2} (\mathbf {1}+ {\mathbf e}_{2k+2})(\mathbf {1}+ {\mathbf e}_{2k+2})^{\top } \left[ \tilde{Y}(k)\right] ^{-1/2} \end{aligned}$$

is a rank one matrix, using (10) we have that the matrix in (11) is PSD if and only if

$$\begin{aligned} 1 \ge \frac{4}{2k+2+\gamma }(\mathbf {1}+ {\mathbf e}_{2k+2})^{\top } [\tilde{Y}(k)]^{-1} (\mathbf {1}+ {\mathbf e}_{2k+2})=\frac{2(\mathbf {1}+ {\mathbf e}_{2k+2})^{\top } u}{2k+2+\gamma }. \end{aligned}$$

(12)

To conclude the above, we used the observation that for every $h \in {\mathbb {R}}^n \setminus \{0\}$,

$$\begin{aligned} I - h h^{\top } \hbox { is PSD iff } \frac{h^{\top }}{\Vert h\Vert _2} \left( I-h h^{\top }\right) \frac{h}{\Vert h\Vert _2} \ge 0.\end{aligned}$$

To see the latter, one can apply a spectral decomposition to the matrix $\left( I-h h^{\top }\right)$, where one of the eigenvectors is $\frac{h}{\Vert h\Vert _2}$.

Now, using the definition of $\tilde{Y}(k)$ we have that

$$\begin{aligned} \tilde{Y}(k) \mathbf {1}= 4 (\mathbf {1}) + (4+ 2 \beta _k ){\mathbf e}_{2k+2}=2\tilde{Y}(k)u+2\beta _k {\mathbf e}_{2k+2}, \end{aligned}$$

and then

$$\begin{aligned} u=\frac{1}{2} \mathbf {1}- \beta _k [\tilde{Y}(k)]^{-1} {\mathbf e}_{2k+2}. \end{aligned}$$

(13)

Therefore,

$$\begin{aligned} 2(\mathbf {1}+ {\mathbf e}_{2k+2})^{\top } u&=2(\mathbf {1}+ {\mathbf e}_{2k+2})^{\top } \left( \frac{1}{2} \mathbf {1}- \beta _k [\tilde{Y}(k)]^{-1} {\mathbf e}_{2k+2}\right) \\&=(2k+3) -2 \beta _k (\mathbf {1}+ {\mathbf e}_{2k+2})^{\top } [\tilde{Y}(k)]^{-1} {\mathbf e}_{2k+2} \end{aligned}$$

and again using (10), we obtain

$$\begin{aligned} 2(\mathbf {1}+ {\mathbf e}_{2k+2})^{\top } u = (2k+3) -\beta _k u_{2k+2}. \end{aligned}$$

(14)

Hence, using (12) and (14) we can conclude that the matrix in (11) is PSD if and only if

$$\begin{aligned} 1\ge \frac{(2k+3) -\beta _k u_{2k+2}}{2k+2+\gamma } \end{aligned}$$

or equivalently, if and only if

$$\begin{aligned} \gamma \ge 1- \beta _k u_{2k+2}.\square \end{aligned}$$

By the previous claims, to prove that $Y(k,\gamma )$ is PSD for some $\gamma \in (0,1)$, it suffices to prove that there exists $\gamma \in (0,1)$ such that

$$\begin{aligned} \gamma \ge 1-\beta _k u_{2k+2}, \end{aligned}$$

where u is the unique solution of (10).

Thus, as long as $u_{2k+2}>0$, we may have $\gamma <1$ as desired. Using (13), we have that

$$\begin{aligned} u_{2k+2}={\mathbf e}_{2k+2}^{\top } u= \frac{1}{2} -\beta _k {\mathbf e}_{2k+2}^{\top } \tilde{Y}(k)^{-1} {\mathbf e}_{2k+2}. \end{aligned}$$

Based on the above expression, we may interpret ${\mathbf e}_{2k+2}^{\top } \tilde{Y}(k)^{-1} {\mathbf e}_{2k+2}$ as the $(2k+2)$nd entry of the unique solution h of the linear system $\tilde{Y}(k) h = {\mathbf e}_{2k+2}$. Now using Cramer’s rule to express this entry as a ratio of two determinants and the definitions of $\tilde{Y}$, $\hat{Y}$, and $A_k$, we conclude

$$\begin{aligned} u_{2k+2}=\frac{1}{2}-\beta _k\frac{A_k(k)}{\det \left( \hat{Y}(k)\right) }. \end{aligned}$$

Then, using the identities (7) and (9), we obtain

$$\begin{aligned} u_{2k+2}= \frac{1}{2}\left[ 1- \beta _k\frac{2k+1-\beta _k}{2-(2k+1)\beta _k-\beta _k^2}\right] . \end{aligned}$$

The numerator of the last ratio above is strictly less than $(2k+1)$ and the denominator is strictly larger than one. Whence, $u_{2k+2}> \frac{1}{4(k+1)}>0$. This completes the proof.$\square$

Utilizing the previous lemma we are able to prove Theorem 18.

Proof of Theorem 18

Recall, we may assume that in $H^k$ the node $2k+1$ is not connected to node 0. Let $\gamma \in (0,1)$ and $x(k,\gamma )=\frac{1}{2k+2+\gamma }(2,2,\dots ,2,4)^{\top }\in {\mathbb {R}}^{2k+2}$ where the ith component of $x(k,\gamma )$ corresponds to node $i-1$ in $H^k$ for $i \in \{1,\ldots ,2k+2\}$. Let $Y^*(k,\gamma ):=\frac{1}{2k+2+\gamma }Y(k,\gamma )$. Then, $Y^*(k, \gamma )$ is a symmetric matrix that clearly satisfies that $Y^*(k, \gamma ){\mathbf e}_0=\text {diag}(Y^*(k, \gamma ))\in {{\mathrm{\text {FRAC}}}}(H^k)$. Moreover, it is not hard to check that, for $i \in \{1,\dots ,2k+2\}$,

$$\begin{aligned} Y^*(k, \gamma ){\mathbf e}_i \in {{\mathrm{cone}}}({{\mathrm{\text {FRAC}}}}(H^k))\; \text { and } \; Y^*(k, \gamma )({\mathbf e}_0-{\mathbf e}_i) \in {{\mathrm{cone}}}({{\mathrm{\text {FRAC}}}}(H^k)). \end{aligned}$$

This proves that $Y^*(k, \gamma )\in M(H^k)$. By the previous lemma, there exists $\bar{\gamma }\in (0,1)$ for which $Y^*(k, \bar{\gamma })\in M_+(H^k)$. Hence, $x(k, \bar{\gamma })\in {{{\mathrm{\text {LS}}}}}_+(H^k)$. It only remains to observe that $x(k,\bar{\gamma })$ violates the rank inequality of $H^k$. Thus, $x(k,\bar{\gamma })\notin {{\mathrm{\text {STAB}}}}(H^k)$.$\square$

5.2 Operations that preserve ${{{\mathrm{\text {LS}}}}}_+$-imperfection

Firstly, we prove Theorem 22 on the k-stretching operation for $k\ge 1$, already stated in Sect. 4. Actually, we will see that the same proof given in [26] for the case $k=0$ can be used for the case $k\ge 1$. Assume that $\tilde{G}$ is obtained from G after the k-stretching operation on node v and let u, $v_1$ and $v_2$ be as in the definition of the operation in Sect. 2.5. For any $x\in {\mathbb {R}}^{V(G)}$, we write $x=\left( \begin{array}{c} \bar{x}\\ x_v \end{array} \right)$ where $\bar{x} \in \mathbb R^{V(G-v)}$.

For the case $k=0$, the authors in [26] prove that if a point $x=\left( \begin{array}{c} \bar{x}\\ x_v \end{array} \right) \in {{{\mathrm{\text {LS}}}}}_+^r(G)$ then the point $\tilde{x}$ given by

$$\begin{aligned} x_w=\left\{ \begin{array}{ll} \tilde{x}_w &{} \text { if } w\in \{u,v_1,v_2\},\\ \bar{x}_w &{} \text { otherwise,} \end{array} \right. \end{aligned}$$

satisfies $\tilde{x} \in {{{\mathrm{\text {LS}}}}}_+^r(\tilde{G})$. In order to do so they prove that if

then

On the other hand, they show that if $\sum _{j \in V(G)} a_j x_j \le \beta$ is a valid inequality for ${{\mathrm{\text {STAB}}}}(G)$, defining $\tilde{\beta } = \beta +a_v$ and

$$\begin{aligned} \tilde{a}_j = \left\{ \begin{array}{lll} a_v &{} &{} \text { if } j \in \{v_1, v_2, u\},\\ &{}&{}\\ a_j &{} &{} \hbox {otherwise,} \end{array} \right. \end{aligned}$$

the inequality $\sum _{j \in V(\tilde{G})} \tilde{a}_j x_j \le \tilde{\beta }$ is valid for ${{\mathrm{\text {STAB}}}}(\tilde{G})$. Moreover, if $x^*$ violates $\sum _{j \in V(G)} a_j x_j \le \beta$ then $\tilde{x^*}$ violates $\sum _{j \in V(\tilde{G})} \tilde{a}_j x_j \le \tilde{\beta }$.

Proof of Theorem 22

It is enough to observe that $\tilde{Y}\in M_+\left( {{\mathrm{\text {LS}}}}^{r-1}(\tilde{G})\right)$ and the inequality $\sum _{j \in V(\tilde{G})} \tilde{a}_j x_j \le \tilde{\beta }$ is valid for ${{\mathrm{\text {STAB}}}}(\tilde{G})$ even for the case that $\tilde{G}$ is obtained after the k-stretching on node v in G, for $k\ge 1$. $\square$

Let us now consider the clique-subdivision operation defined in [4]. For $x \in {\mathbb {R}}^n$, let $\bar{x} \in {\mathbb {R}}^{n+2}$ such that $\bar{x}_i=x_i$ for every $i \in \{1,\ldots ,n\}$, $\bar{x}_{n+1}=x_2$ and $\bar{x}_{n+2}=x_1$, and write $\bar{x}=\left( \begin{array}{c} x\\ x_2\\ x_1 \end{array}\right)$. In [4] the authors prove that if $\tilde{G}$ is obtained from G by the clique subdivision of the edge $v_1 v_2$ in the clique K and $x\in {{{\mathrm{\text {LS}}}}}_+^k(G)$ then $\bar{x}\in {{\mathrm{\text {LS}}}}^k(\tilde{G})$. In order to do so, they show that if $Y{\mathbf e}_0=\left( \begin{array}{c} 1 \\ x \end{array}\right)$ for

(15)

then

(16)

Proof of Theorem 23

It is enough to observe that if the matrix Y is PSD then so is the matrix in (16).$\square$

6 Conclusions and further results

In this work, we face the problem of characterizing the stable set polytope of ${{{\mathrm{\text {LS}}}}}_+$-perfect graphs, a graph class where the Maximum Weight Stable Set Problem is polynomial-time solvable. This class strictly includes many well-known graph classes such as perfect graphs, t-perfect graphs, wheels, anti-holes, near-bipartite graphs and the graphs obtained from various suitable compositions of these. The stable set polytope of either a perfect or a near-bipartite graph only needs the inequalities associated with the stable set polytopes of its near-bipartite subgraphs. We have conjectured that the same holds for all ${{{\mathrm{\text {LS}}}}}_+$-perfect graphs. In this paper, we prove the validity of this conjecture for ${\mathrm {fs}}$-perfect graphs, a superclass of near-perfect graphs. Moreover, if $\mathcal {FS}$ denotes the class of ${\mathrm {fs}}$-perfect graphs, using the definition in (1), we actually prove that the conjecture holds for a superclass of ${\mathrm {fs}}$-perfect graph defined as those graphs for which $\mathcal {FS}(G)={{\mathrm{\text {STAB}}}}(G)$. Observe that the graph in Fig. 4 satisfies $\mathcal {FS}(G)={{\mathrm{\text {STAB}}}}(G)$ and it is not ${\mathrm {fs}}$-perfect.

Fig. 4

A graph G satisfying $\mathcal {FS}(G)={{\mathrm{\text {STAB}}}}(G)$ which is not ${\mathrm {fs}}$-perfect

Also, the results used in the proof of the Theorem 25 allow us to conclude the following:

Corollary 29

Let G be a graph such that $V(G)=\{0,1,\ldots ,2k+1\}$ with $k\ge 2$ and $G-0$ is minimally imperfect. Then:

• If $G-0=C_{2k+1}$ then G is ${{{\mathrm{\text {LS}}}}}_+$-perfect if and only if either $\delta _G(0)\ge 2$ and G has only one odd central cycle or $\delta _G(0)\in \{0,1,2k+1\}$.

• If $G-0=\overline{C_{2k+1}}$ with $\alpha (G)=2$ then G is ${{{\mathrm{\text {LS}}}}}_+$-perfect if and only $\delta _G(0)=2k+1$.

From the above characterization, we identify some of the forbidden structures in the family of ${{{\mathrm{\text {LS}}}}}_+$-perfect graphs:

Corollary 30

Let G be an ${{{\mathrm{\text {LS}}}}}_+$-perfect graph. Then, there is no subgraph $G'$ of G such that

• $G'-v_0=C_{2k+1}$, $2\le \delta _{G'}(v_0)\le 2k$ and $G'$ has at least two odd central cycles, or

• $G'-v_0=\overline{C_{2k+1}}$ and $k+1 \le \delta _G'(v_0)\le 2k$ and $\alpha (G')=2$,

for some $v_0\in V(G')$ and $k\ge 2$.