Lovász and Schrijver $N_+$-Relaxation on Web Graphs

Abstract

In this contribution we continue the study of the Lovász-Schrijver PSD-operator applied to the edge relaxation of the stable set polytope of a graph. The problem of obtaining a combinatorial characterization of graphs for which the PSD-operator generates the stable set polytope in one step has been open since 1990. In an earlier publication, we named these graphs $N_+$-perfect. In the current work, we prove that the only imperfect web graphs that are $N_+$-perfect are the odd-cycles and their complements. This result adds evidence for the validity of the conjecture stating that the only graphs which are $N_+$-perfect are those whose stable set polytope is described by inequalities with near-bipartite support. Finally, we make some progress on identifying some minimal forbidden structures on $N_+$-perfect graphs which are also rank-perfect.

Partially supported by grants PIP-CONICET 241, PICT-ANPCyT 0361, PID UNR 415, PID UNR 416.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Perfect graphs were introduced by Berge in the early sixties [1]. A graph is perfect if each of its induced subgraphs has chromatic number equal to the cardinality of a maximum cardinality clique in the subgraph.

According to the results in [6] the family of perfect graphs constitute a class where the Maximum Weighted Stable Set Problem (MWSSP) can be solved in polynomial time. Some years later, the same authors proved a beautiful result [8]: for every graph $G$,

$$\begin{aligned} \begin{array}{l} G \mathrm{~is~ perfect } \Leftrightarrow \text {TH}(G)=\text {STAB}(G) \Leftrightarrow \text {TH}(G)=\text {CLIQUE}(G) \Leftrightarrow \\ \text {STAB}(G)=\text {CLIQUE}(G) \Leftrightarrow \text {TH}(G) \mathrm{~is~polyhedral, } \end{array} \end{aligned}$$

(1)

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

In the early nineties, Lovász and Schrijver introduced the PSD-operator $N_+$ which, applied over the edge relaxation of $\text {STAB}(G)$, generates the positive semidefinite relaxation $N_+(G)$ stronger than $\text {TH}(G)$ [11].

As it holds for perfect graphs, MWSSP can be solved in polynomial time for the class of graphs for which $N_+(G)=\text {STAB}(G)$. We will call these graphs $N_+$-perfect.

Our main goal is to obtain a characterization of $N_+$-perfect graphs similar to the one given in (1) for perfect graphs. More precisely, we would like to find an appropriate polyhedral relaxation of $\text {STAB}(G)$ playing the role of $\text {CLIQUE}(G)$ in (1). Following this line, in a recent publication [3], we proposed the following conjecture:

Conjecture 1

The stable set polytope of every $N_+$-perfect graph can be described by facet inducing inequalities with near-bipartite support.

In [2] the validity of this conjecture on near-perfect graphs is established. In fact, the following theorem is proved.

Theorem 1

[2]. Let $G$ be an $N_+$-perfect and a properly near-perfect graph. Then, either $G$ or its complement is an odd cycle.

Later, in [3] we extended its validity to ${\mathrm {fs}}$-perfect graphs, a superclass of near-perfect graphs defined as those graphs for which the stable set polytope is completely described by clique constraints and a single full-support inequality.

The main contribution of this paper is to prove the validity of the conjecture on one more infinite family of graphs, the web graphs.

2 Preliminaries

Given a graph $G=(V,E)$ a stable set is a subset of mutually non-adjacent nodes in $G$. The maximum cardinality of a stable set is denoted by $\alpha (G)$, the stability number of $G$. The stable set polytope is the convex hull of the incidence vectors of the stable sets in the graph $G$ and it is denoted by $\text {STAB}(G)$.

The polyhedron

$$ \text {FRAC}(G)=\{x\in [0,1]^V: x_i+x_j\le 1 \text{ for } \text{ every } ij\in E\} $$

is the edge relaxation of $\text {STAB}(G)$.

A clique $Q$ is a subset of pairwise adjacent nodes in $G$. Every incidence vector of a stable set must satisfy clique constraints, i.e., $\sum _{i\in Q} x_i\le 1$. These constraints define the clique relaxation of the stable set polytope, $\text {CLIQUE}(G)$. In general, $\text {STAB}(G)\subset \text {CLIQUE}(G)$. Chvatal [5] showed that perfect graphs are exactly those graphs for which equality holds.

Minimally imperfect graphs are those graphs that are not perfect but after deleting any node they become perfect. The Strong Perfect Graph Theorem states that the only minimally imperfect graphs are the odd cycles and their complements [4].

The support of a valid inequality for $\text {STAB}(G)$ is the subgraph induced by the nodes having positive coefficient in it. We say that an inequality is a full-support inequality if its support is the whole graph.

In [14] Shepherd called a graph $G$ near-perfect if its stable set polytope is defined only by non-negativity constraints, clique constraints and the full-rank constraint

$$ \sum _{u\in V} x_u\le \alpha (G). $$

Clearly, every node induced subgraph of a near-perfect graph is also near-perfect [14].

Due to results of Chvátal [5] near-perfect graphs constitute a superclass of perfect graphs. According to Padberg [13] minimally imperfect graphs are also near-perfect graphs.

Near-bipartite graphs, defined in [15], are those graphs such that removing all neighbours of an arbitrary node and the node itself, leaves the resulting graph bipartite.

Given integer numbers $k$ and $n$ such that $n\ge 2(k+1)$, the web graph, denoted by $W_n^k$, is the graph having node set $\{1,\dots ,n\}$ and such that $ij$ is an edge if $i$ and $j$ differ by at most $k$ (mod $n$) and $i\ne j$.

If $k=1$, $W_n^1$ is a cycle. If $k\ge 2$ and $n\le 2k+2$ $W_n^k$ is a perfect graph and $W_{2k+3}^k$ is the complementary graph of the $(2k+3)$-cycle.

In [18] Wagler characterized all near-perfect web graphs:

Theorem 2

[18]. A web graph is near-perfect if and only if it is perfect, an odd hole, the web $W^2_{11}$ or it has stability number 2.

If $W_{n'}^{k'}$ is a node induced subgraph of $W_n^k$ then it is a subweb of $W_n^k$. In [17] Trotter characterized for which values of $n'$ and $k'$, $W_{n'}^{k'}$ is a subweb of $W_n^k$.

Theorem 3

[17]. If $k\ge 1$ and $n\ge 2(k+1)$ the graph $W_{n'}^{k'}$ is a subweb of $W_n^k$ if and only if

$$ \frac{k'}{k}\le \frac{n'}{n}\le \frac{k'+1}{k+1}. $$

2.1 The $N_+$-Operator

As we have already mentioned, in this paper we focus on the behaviour of the $N_+$-operator defined by Lovász and Schrijver [11] on the edge relaxation of the stable set polytope.

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), ${\mathbf {1}}$ the vector with all components equal to 1 and ${\mathbb S}_+^{n}$ the space of $n$-by-$n$ symmetric and positive semidefinite matrices with real entries.

Given a convex set $K$ in $[0,1]^n$, let

$$ \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 \right\} . $$

Then, we define the polyhedral set

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

where $\mathrm{diag}(Y)$ denotes the vector whose $i$-th entry is $Y_{ii}$, for every $i=0,\dots ,n$.

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

$$ N_+(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\} . $$

In practice, we prove that a point $x\in [0,1]^n$ belongs to $N_+(K)$ by showing the existence of a symmetric PSD matrix $Y$ of the form

(2)

where $x^t$ stands for the transpose of column vector $x$ and $\bar{Y}$ is an $n \times n$ matrix with columns $\bar{Y}_i$ for $i=1,\dots ,n$, satisfying the following conditions:

• 1. $\bar{Y}_{ii}=x_i$,

• 2. If $x_i=0$ then $\bar{Y}_i={\mathbf {0}}$,

• 3. If $x_i=1$ then $\bar{Y}_i=x$,

• 4. If $0<x_i<1$ then $\frac{1}{x_i}\bar{Y}_i \in K$ and $\frac{1}{1-x_i}(x-\bar{Y}_i) \in K$,

for every $i=1,\dots ,n$.

In [11], Lovász and Schrijver proved that $N_+(K)$ is a relaxation of the convex hull of integer solutions in $K$.

If we let $N_+^0(K)=K$ then $k$-th application of the $N_+$-operator is $N_+^k(K)=N_+(N_+^{k-1}(K))$ for every $k\ge 1$. The authors in [11] showed that $N_+^n(K)=\mathrm{conv}(K\cap \{0,1\}^n)$.

In this work we focus on the behaviour of a single application of the $N_+$-operator on the edge relaxation of the stable set polytope of a graph. Then, in order to simplify the notation we write $N_+(G)=N_+(\text {FRAC}(G))$.

In [11] it is shown that

$$ \text {STAB}(G)\subset N_+(G)\subset \text {TH}(G)\subset \text {CLIQUE}(G). $$

Also from results in [11], we know that graphs for which every facet defining inequality of $\text {STAB}(G)$ has a near-bipartite support is $N_+$-perfect. Then, Conjecture 1 establishes that these graphs are the only $N_+$-perfect graphs.

In particular, perfect and near-bipartite graphs are $N_+$-perfect. In addition, it can be proved that every subgraph of an $N_+$-perfect graph is also $N_+$-perfect. A graph $G$ that is not $N_+$-perfect is called $N_+$ -imperfect.

Using the properties of the $N_+$-operator, if $G'$ is an $N_+$-imperfect subgraph of $G$ then $G$ is also $N_+$-imperfect.

In [7] and [9] it was proved that all the imperfect graphs with at most $6$ nodes are $N_+$-perfect graphs, except for the two imperfect near-perfect graphs depicted in Fig. 1. The graph on the left is denoted by $G_{LT}$ and the other one is denoted by $G_{EMN}$.

Fig. 1.

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

A graph $G'$ is an odd subdivision of a graph $G$ if it is obtained by replacing an edge of $G$ by a path of odd length.

As a consequence of the results in [9] we have the following:

Lemma 1

If $G$ is $N_+$-imperfect and $G'$ is obtained after the odd subdivision of an edge in $G$, then $G'$ is also $N_+$-imperfect.

This result becomes relevant in the proof of the validity of the conjecture on web graphs since there we show that most of the web graphs have an odd subdivision of the graph $G_{LT}$ as a node induced subgraph.

3 The Conjecture on Web Graphs

The fact that the conjecture holds on web graphs will follow after proving that the only $N_+$-perfect webs are either perfect or minimally imperfect webs.

Theorem 1 [2] asserts that every near-perfect graph satisfies the conjecture, therefore, from Theorem 2, we only need to consider web graphs with stability number at least three. It is known that the stability number of $W_n^k$ is $\alpha (W_n^k) = \left\lfloor \frac{n}{k+1}\right\rfloor$. Then, if $n\le 3k+2$, $W_n^k$ is near-perfect and from Theorem 1 the conjecture holds on these web graphs. Therefore, from now on we can consider web graphs $W^k_n$ with $n\ge 3k+3$.

Now we are able to present the following result:

Theorem 4

If $n\ge 9$ and $n\ne 10$, $W^2_n$ has an odd subdivision of $G_{LT}$ as a node induced subgraph.

Proof

Let $n\ge 9$ and $\{1,\dots ,n\}$ be the node set of $W_n^2$. Assume that we delete the six consecutive nodes in the set $\{n-5,n-4,\dots , n\}$. Note that if we find a subset $T^s= \{v_1,\dots , v_{2s}\}$ of $\{1,\dots , n-6\}$, with $s\ge 1$, $v_1=1$, $v_{2s}=n-6$ and such that $T^s$ induces a path in $W_n^2$, then $T^s \cup \{ n-4,n-3,n-2,n-1\}$ induces in $W_n^2$ an odd subdivision of $G_{LT}$.

For example, in the web $W^2_{14}$ the set $T^3=\{1,2,4,5,7,8\}$ induces a path and $T^3\cup \{10,11,12,13\}$ induces an odd subdivision of $G_{LT}$. See Fig. 2.

Fig. 2.

The web graph $W_{14}^2$ and a node induced odd subdivision of $G_{LT}$.

Then, in order to prove the result we show the existence of such a set $T^s$ with the above required properties for every $n\ge 9$ and $n\ne 10$.

We divide the rest of the proof into four different cases according to the value of $n-6$.

• If $n-6=4r+3$ for some $r\ge 0$, then

  $$ T^{r+1}=\{2t-1: 1\le t\le 2r+2\}. $$

• If $n-6= 4r+2$ then $r\ge 1$ since $n\ge 9$. In this case, we consider

  $$ T^{r+1}=\{2t-1: 1\le t\le 2r+1\}\cup \{n-6\}. $$

• If $n-6= 4r+1$ again $r\ge 1$. In this case, we find

  $$ T^{r+1}=\{2t: 1\le t\le 2 r\}\cup \{1,n-6\}. $$

• If $n-6= 4r$ we have $r\ge 2$ since $n\ge 9$ and $n\ne 10$. In this case we consider

  $$ T^{r+1}=\{3+ 2t: 1\le t\le 2r-2\}\cup \{1,2,4,n-6\}. $$

   $\square$

Corollary 1

If $n\ge 8$ and $n\ne 10$ then $W^2_n$ is $N_+$-imperfect.

Proof

The web graph $W_8^2$ is an imperfect near-perfect graph and then it is $N_+$-imperfect.

Since every odd subdivision of $G_{LT}$ is $N_+$-imperfect and the $N_+$-imperfection of a subgraph implies the $N_+$-imperfection of the graph itself, the result follows directly from the previous theorem.    $\square$

In order to complete the analysis of the family of web graphs $W_n^2$ we need to prove that $W_{10}^2$ is $N_+$-imperfect. Note that it does not have an odd subdivision of $G_{LT}$ as a node induced subgraph. Instead, we make use of the definition of $N_+(W_{10}^2)$.

Lemma 2

The web graph $W^2_{10}$ is $N_+$-imperfect.

Proof

The proof is based on finding a point $\bar{x} \in N_+(W_{10}^2) \setminus \text {STAB}(W_{10}^2)$.

Let us consider the point $\bar{x}=\lambda {\mathbf {1}}\in \text {FRAC}(W_{10}^2)$ for $\lambda =\frac{31}{100}$. Clearly it violates the full-rank constraint and therefore, $\bar{x}\notin \text {STAB}(W_{10}^2)$.

In order to prove that $\bar{x} \in N_+(W_{10}^2)$ we present a matrix $Y$ as in (2) which represents the point in the higher dimensional space.

For this purpose we make use of the following definition.

Let $T: {\mathbb R}^n\rightarrow {\mathbb R}^n$ be such that $T(v_1,\ldots ,v_n)=(v_n,v_1,\ldots ,v_{n-1})$. The matrix $\mathrm{circ}(u)$ is the $n \times n$-matrix whose first row is $T^0(u)=u$ and whose $j$-th row is given by $T^{j-1}(u)=T(T^{j-2}(u))$, for every $j\ge 2$.

Let $z=(\lambda ,0,0,\beta ,\gamma ,\delta ,\gamma ,\beta ,0,0)$ where

$$ \gamma =\frac{853}{10000}, \quad \delta =\frac{336}{10000} \quad \text { and } \quad \beta =\frac{2234}{10000}. $$

If $\bar{Y}=\mathrm{circ}(z)$ then it is not difficult to check that $Y\in {\mathbb R}^{11}$ defined as in (2) is PSD and it satisfies that

$$ \frac{1}{\lambda }\bar{Y}_i \in \text {FRAC}(W^2_{10}) \quad \text { and } \quad \frac{1}{1-\lambda }(\lambda {\mathbf {1}}-\bar{Y}_i) \in \text {FRAC}(W^2_{10}). $$

   $\square$

The following result implies that Conjecture 1 holds for web graphs.

Theorem 5

If the web graph $W^k_n$ is $N_+$-perfect then it is either a perfect or a minimally imperfect graph.

Proof

Due to the fact that the conjecture is proved for near-perfect graphs (Theorem 1) we only need consider those webs which are not near-perfect and prove that none of them are $N_+$-perfect.

If the web $W_n^k$ is not near-perfect then $k\ge 2$ and $n\ge 3k+3$.

If $k=2$ the result follows from Corollary 1 and Lemma 2.

Let $k\ge 3$ and $n\ge 3k+3$. We will prove that every web $W_n^k$ has a subweb of the form $W^2_{n'}$ for some $n'\ge 8$.

After Trotter’s result (Theorem 3) $W^2_{n'}$ is a subweb of $W_n^k$ if

$$ \frac{2n}{k}\le n' \le \frac{3n}{k+1}. $$

Let $\varDelta ^k (n)= \frac{3n}{k+1}- \frac{2n}{k}= n \frac{k-2}{k(k+1)}$.

Observe that $\varDelta ^k(n)$ assumes its minimum value when $n$ is minimum, i.e. when $n=3k+3$. In this case, $\varDelta ^k (n)= \frac{3 (k-2)}{k}\ge 1$. Then, for every value of $n\ge 3k+3$ we can find an integer $n'$ satisfying

$$\begin{aligned} \frac{2n}{k}\le n' \le \frac{3n}{k+1} \end{aligned}$$

and then $W^2_{n'}$ is a subweb of $W_n^k$.

Moreover, since $n\ge 3k+3$ we have that $\left\lfloor \frac{3n}{k+1}\right\rfloor \ge 9$ and $W_n^k$ has a subweb $W^2_{n'}$ for some $n'\ge 8$.

Finally, Corollary 1 and Lemma 2 prove the result.   $\square$

4 On minimally $N_+$-imperfect subgraphs

In [2] we proved the validity of the conjecture on the family of near-perfect graphs. Rank-perfect graphs constitute a superclass of near-perfect graphs, then it seems natural to continue our work towards proving the conjecture on this family. In fact, while studying the $N_+$-perfect graphs which are also near-perfect graphs we could identify some minimal forbidden structures on this family.

We say that a graph is minimally $N_+$-imperfect if it is $N_+$-imperfect but deleting any node leaves an $N_+$-perfect graph. The results in [2] give the minimally $N_+$-imperfect graphs in the family of near-perfect graphs. In order to present them let us introduce some more definitions.

We denote by $C_{2k+1}$ the cycle having node set $\{1,\dots ,2k+1\}$ and edge set $\{i(i+1): i\in \{1,\dots ,2k\}\cup \{1(2k+1)\}$.

In [2] we consider two families of near-perfect graphs, named ${\mathcal {W}}^k$ and ${\mathcal {H}}^k$ for each $k\ge 2$.

Let ${\mathcal {H}}^2={\mathcal {W}}^2=\{G_{LT},G_{EMN}\}$. For $k\ge 3$, ${\mathcal {W}}^k$ is the family of graphs with node set $\{0,1,\dots ,2k+1\}$ such that:

• $G-0=C_{2k+1}$;

• there is no pair of consecutive nodes (in $C_{2k+1}$) with degree $2$;

• the degree of node $0$ is $k+2$.

For $k\ge 3$, ${\mathcal {H}}^k$ is the family of graphs having node set $\{0,1,\dots ,2k+1\}$ such that:

• $G-0$ is the complement of $C_{2k+1}$;

• there is no pair of consecutive nodes (in $C_{2k+1}$) with degree $2k-2$;

• the degree of node $0$ is at most $2k$.

In Fig. 3 we have represented one of the graphs in the family ${\mathcal {W}}^9$ and one of the graphs in the family ${\mathcal {H}}^9$.

Fig. 3.

A graph in the family ${\mathcal {W}}^9$ and ${\mathcal {H}}^9$.

Using the results in [2] we have the following

Lemma 3

Let $G$ be a minimally $N_+$-imperfect graph. If $G$ is a near-perfect graph then it is an odd subdivision of a graph in ${\mathcal {H}}^k \cup {\mathcal {W}}^k$ for some $k\ge 2$.

In this contribution it was important to identify the odd subdivisions of $G_{LT}$ as minimally $N_+$-imperfect structures in the webs, except for $W^2_{10}$.

In fact, we have proved that the web $W^2_{10}$ is a minimally $N_+$-imperfect rank-perfect graph which is not near-perfect. This shows some advance in order to characterize $N_+$-perfect rank-perfect graphs and also a line for our future research.