%VERSION REVISEE
% revised version for SIOPT prepared in May 2001 with SIAM Macros
\documentclass[final]{siamltex}
\usepackage{amsfonts}
\topmargin 0pt
\textheight 8in
\textwidth 5.4in
\evensidemargin 1mm
\newcommand{\oR}{{\rm\bf R}}
\newcommand{\oQ}{{\rm\bf Q}}
\newcommand{\oZ}{{\rm \bf Z}}
\bibliographystyle{plain}
\newcommand{\ds}{\displaystyle}
\newcommand{\conv}{{\rm conv}}
\def\1set{{\rm \hbox{1\hskip-0.37em 1}}}
\newcommand{\FRAC}{{\rm FRAC}}
\newcommand{\STAB}{{\rm STAB}}
\newcommand{\ODD}{{\rm ODD}}
\newcommand{\TTH}{{\rm TH}}
\newcommand{\dd}{\delta}
\newcommand{\RR}{{\cal R}}
\newcommand{\PP}{{\cal P}}
%\newcommand{\SSS}{{\cal S}}
\newcommand{\BB}{{\cal B}}
\newcommand{\AAA}{{\cal A}}
\newcommand{\LL}{{\cal L}}
\newcommand{\GG}{{\cal G}}
\newcommand{\mr}{{\rm mr}}
\newcommand{\MR}{{\rm MR}}
%\newcommand{\rank}{{\rm rank}}
%\newcommand{\diag}{{\rm diag}}
\newcommand{\CC}{{\cal C}}
\newcommand{\EE}{{\cal E}}
\newcommand{\CCt}{\tilde {\cal C}}
\newcommand{\MM}{{\cal M}}
\newcommand{\FF}{{\cal F}}
\newcommand{\MMt}{\tilde {\cal M}}
\newcommand{\svec}{{\rm svec}}
\newcommand{\svecol}{{\rm svec}}
\newcommand{\smatol}{{\rm smat}}
\newcommand{\CUT}{{\rm CUT}}
\newcommand{\MET}{{\rm MET}}
\newcommand{\gap}{{\rm gap}}
\newcommand{\Sym}{{\cal S}}
\newcommand{\Symm}{{\cal S}^1}
\newcommand{\PSD}{{\rm PSD}}
\begin{document}
\title{Tighter Linear and Semidefinite Relaxations for Max-Cut Based on the Lov\'asz-Schrijver Lift-and-Project Procedure}
\author{Monique Laurent
\thanks{CWI, Kruislaan 413, 1098 SJ Amsterdam, The Netherlands
({\tt monique@cwi.nl}).}}
\maketitle
\begin{abstract}
We study how the lift-and-project method introduced by
Lov\'asz and Schrijver \cite{LS91}
applies to the cut polytope.
We show that the cut polytope of a graph can be found in $k$ iterations
if there exist $k$ edges whose contraction produces a graph with no $K_5$-minor.
Therefore,
for a graph $G$ with $n\ge 4$ nodes with stability number $\alpha(G)$, $n-4$ iterations
suffice instead of the $m$ (number of edges) iterations required in general and,
under some assumption,
$n-\alpha(G)-3$ iterations suffice.
The exact number of needed iterations is determined for small $n\le 7$
by a detailed analysis of the new relaxations.
If positive semidefiniteness is added to the construction, then one finds in one
iteration
a relaxation of the cut polytope which is tighter than its basic
semidefinite relaxation and than another one introduced recently by
Anjos and Wolkowicz \cite{AW00}.
We also show how the Lov\'asz-Schrijver relaxations for the stable set polytope of $G$
can be strenghtened using the corresponding relaxations for the cut polytope
of the graph $G^\nabla$ obtained from $G$ by adding a node adjacent to
all nodes of $G$.
\end{abstract}
\begin{keywords}
linear relaxation, semidefinite relaxation,
lift and project, cut polytope, stable set polytope
\end{keywords}
\begin{AMS}
05C50, 15A57, 52B12, 90C22, 90C27
\end{AMS}
\pagestyle{myheadings}
\thispagestyle{plain}
\markboth{M. LAURENT}{LIFT AND PROJECT RELAXATIONS FOR MAX-CUT}
\section{Introduction}
Lov\'asz and Schrijver \cite{LS91} have introduced a
method for constructing a higher dimensional convex set
whose projection $N(K)$ approximates the convex hull $P$ of
the $0-1$ valued points in a polytope $K$ defined by
a given system of linear inequalities. If the
linear system is in $d$ variables, the convex set
consists of symmetric matrices of order $d+1$
satisfying certain linear conditions. A fundamental
property of the projection $N(K)$ is that one can optimize over it in polynomial time and, thus,
find an approximate solution to the original problem in polynomial time.
Moreover, after $d$ iterations of the operator $N$, one finds
the polytope $P$.
Lov\'asz and Schrijver \cite{LS91}
also introduce some strengthenings of the basic construction; in particular,
adding positive semidefinite constraints leads to the operator $N_+$
and adding stronger linear conditions in the definition
of the higher dimensional set of matrices leads
to the operators $N'$ and $N'_+$.
They study in detail how the method applies
to the stable set polytope. Starting with $K=\FRAC(G)$
(the {fractional stable set polytope} defined by nonnegativity and the edge constraints),
they show that in one iteration of the $N$ operator one obtains all
odd hole inequalities (and no more) while, in one iteration of the $N_+$
operator, one obtains many inequalities including odd wheel, clique, odd antihole inequalities and orthogonality constraints;
therefore, the relaxation $N_+(\FRAC(G))$
is tighter than the basic semidefinite relaxation of the stable set polytope
by the theta body $\TTH(G)$. In
particular, the
method permits to solve the maximum stable set problem
in a $t$-perfect graph or in a perfect graph in polynomial time.
They also show that the stable set polytope of $G$ is found after
at most $n-\alpha(G)-1$ iterations of the
$N$ operator (resp. $\alpha(G)$ iterations of the $N_+$ operator)
applied to $\FRAC(G)$ if $G$ has at least one edge.
On the other hand, there exist `easy' polytopes $P$
(meaning that their linear description is known and one can optimize over them in polynomial time)
for which the number of iterations of the $N$ or $N_+$ operators
needed in order to find $P$ grows linearly with the dimension of $P$. For example,
Stephen and Tun\c{c}el \cite{ST99} show that $n$ iterations
are needed for finding the matching polytope
of $K_{2n+1}$ (starting with the polytope defined by nonnegativity and the degree constraints)
using the $N_+$ operator. Recently, Cook and
Dash \cite{CD00} and Goemans and Tun\c{c}el \cite{GT00}
construct examples where positive semidefiniteness does not help;
namely, the same number $d$ of iterations is needed for finding
some $d$-dimensional polytope $P$ using the $N$ or the $N_+$ operator.
This is the case, for instance, for the
polytope $P:=\{x\in \oR^d\mid \sum_{i=1}^dx_i\ge 1\}$ if we start
from its relaxation $K:=\{x\in \oR^d\mid \sum_{i=1}^dx_i\ge {1\over 2}\}$.
In this paper we study how the method applies to the cut polytope
when starting with its linear relaxation by the metric polytope
$\MET(G)$ (to be defined later).
When using the operator $N_+$, one obtains in one iteration a semidefinite relaxation
of the cut polytope which is tighter than its basic
semidefinite relaxation
as well as than a refinement of it introduced
recently by Anjos and Wolkowicz \cite{AW00}.
One can, in fact, refine the relaxation $N(\MET(G))$
by first applying the $N$ operator to the metric polytope
of the complete graph and then projecting on the edge set of the graph;
the relaxation denoted as $N(G)$ obtained in this way satisfies:
$\CUT(G)\subseteq N(G)\subseteq N(\MET(G))$.
We consider in this paper both constructions $N(G)$ and $N(\MET(G))$,
also for the stronger operators $N_+,N',N'_+$ and their iterates.
We show that $\CUT(G)=N^k(\MET(G))$ if there
exist $k$ edges in $G$ whose contraction produces
a graph with no $K_5$-minor. In particular,
the cut polytope of a graph on $n$ nodes
can be found after $n-4$ (resp. $n-5$)
iterations of the $N$ (resp. $N'$) operator if $n\ge 4$ (resp. $n\ge 6$)
(while the cut polytope has dimension $m$, the number of edges of the graph).
Moreover, if $G$ has stability number $\alpha(G)$, then
$\CUT(G)=N^k(G)$ where $k:=\max(0,n-\alpha(G)-3)$; equality
$\CUT(G)=N^k(\MET(G))$ holds if there exists a maximum stable set in $G$ whose complement induces a graph with at most three connected
components.
The upper bound $n-\alpha(G)-3$ is similar
to the upper bound of \cite{LS91} for the stable set polytope.
It is well known that the stable set polytope
$\STAB(G)$ can be realized as a face
of the cut polytope $\CUT(G^\nabla)$, where $G^\nabla$ is obtained by
adding a new node to $G$ adjacent to all nodes of $G$; moreover,
an analogue relation exists between their basic linear and positive semidefinite relaxations.
We study how this fact extends to their relaxations obtained via the
Lov\'asz-Schrijver procedure.
Namely, we show that $N^k(\MET(G^\nabla))$ (resp.
$\nu^k(\MET(G^\nabla))$)
yields a relaxation of $\STAB(G)$ which is tighter than
$N^{k+1}(\FRAC(G))$ (resp. $\nu^k(\FRAC(G))$ for $\nu=N_+,N',N_+'$).
Although the inclusion $N_+(\MET(G))\subseteq N(\MET(G))$ is strict
for certain graphs (e.g., for any complete graph on $n\ge 6$ nodes),
we do not know an example of a graph $G$ for which the number of iterations needed
for finding $\CUT(G)$ is smaller when using the operator $N_+$ than when
using the operator $N$.
This contrasts with the case of the stable set polytope where, for instance,
$\STAB(K_n)$ is found in one iteration of the $N_+$ operator applied to
$\FRAC(G)$ while $n-2$ iterations
of the $N$ operator are needed.
\medskip
The paper is organized as follows.
We give in Section \ref{secLS} a general description of the
Lov\'asz-Schrijver (LS) procedure and
Section \ref{secrelax} contains a presentation of the various relaxations of the cut polytope
considered in the paper. In Section \ref{secprop},
we study the index of a graph (the smallest number
of iterations of the LS procedure needed for finding its cut polytope);
upper bounds are proved in Sections \ref{secbound} and \ref{secboundN'},
the behaviour of the index under taking graph minors and clique sums
is investigated in Section \ref{secminor} and Section \ref{sectool}
contains a number of needed technical tools.
We study in Section \ref{secvalidity} the validity of hypermetric inequalities
for the new relaxations, which enables us to determine the
exact value of the index of a graph on $n\le 7$ nodes;
some technical proofs are delayed till Section \ref{secproof}.
We finally study in Section \ref{secstable} the links between the LS relaxations
for the cut polytope and the original LS relaxations
for the stable set polytope.
\section{The Lov\'asz-Schrijver Procedure}\label{secLS}
Let $F\subseteq \{\pm 1\}^d$, let $P:=\conv(F)$ be the
integral polytope whose linear description one wishes to find, and let
$$K=\{x\in \oR^d\mid Ax\ge b\}$$ be a linear relaxation of
$P$ such that $K\subseteq [-1,1]^d$ and $K\cap \{\pm 1\}^d=F$
($K$ is a {\em linear programming formulation} for $P$).
Starting from $K$, the LS method constructs a hierarchy of linear
relaxations for $P$ which in $d$ steps finds the exact description
of $P$. The basic idea is as follows:
If we multiply an inequality $a^Tx\ge \beta$ valid for $F$ by
$1\pm x_i\ge 0$ we obtain two nonlinear inequalities which remain
valid for $F$.
Applying this to all the inequalities from the system $Ax\ge b$, substituting
$x_i^2$ by 1 and linearizing $x_ix_j$ by a new variable $y_{ij}$ for $i\ne j$,
we obtain a polyhedron in the $d+1\choose 2$-space whose projection
$N(K)$ on the
original $d$-space contains $P$ and is contained in $K$.
The method was described in \cite{LS91} in terms of 0-1 variables, but for our application to the max-cut problem it is more
convenient to work with $\pm 1$ variables which is why we present it here in this setting.
%The above described construction is identical to the first step
%of the method of Sherali and Adams \cite{SA90}; however the two methods differ
%in the way of iterating the basic step.
It is useful to reformulate the construction in matrix terms.
First we introduce some notation.
As it is often more convenient to work with homogeneous systems of inequalities, i.e.,
with cones rather than polytopes, one embeds the $d$-space
into $\oR^{d+1}$ as the hyperplane: $x_0=1$.
%The following notation will be useful:
For a polytope $P$ in $\oR^d$,
$\tilde P:=\{\lambda(1,x)\mid x\in P,\lambda \ge 0\}$ denotes the
cone in $\oR^{d+1}$ obtained by homogenization of $P$; thus
$P=\{x\in \oR^d\mid (1,x)\in \tilde P\}$.
%and, for a cone $K$ in $\oR^{d+1}$, $\tilde K:=\{x\mid (1,x)\in K\}$
%is a polytope in $\oR^d$; thus, $\tilde {\tilde P}=P$ and $\tilde {\tilde K}=K$.
Given a cone $K$, its {\em dual cone} $K^*$
is defined as
$$K^*=\{y\mid y^Tx\ge 0 \ \forall x\in K\}.$$
Consider the cube $Q:=[-1,1]^d$ and its homogenization
$\tilde Q=\{(x_0,x)\in \oR^{d+1}\mid -x_0\le x_i\le x_0 \ \forall i=1,\ldots,d\}$.
Thus the dual cone of $\tilde Q$ is generated
by the $2d$ vectors $e_0\pm e_i$ ($i=1,\ldots,d$), where
$e_0,e_1,\ldots,e_d$ denote the standard unit vectors in $\oR^{d+1}$.
Given two polytopes $K_1\subseteq K_2\subseteq Q$,
let $M(K_1,K_2)$
denote the set of symmetric matrices
$Y=(y_{ij})_{i,j=0}^d$ satisfying the following conditions (\ref{reli})-(\ref{relii}):
\begin{equation}\label{reli}
y_{i,i}=y_{0,0} \mbox{ for } i=1,\ldots,d,
\end{equation}
\begin{equation}\label{relii}
Y {\tilde K_2}^* \subseteq {\tilde K_1}
% Y(e_0\pm e_i)\in \tilde K \mbox{ for } i=1,\ldots,d
\end{equation}
and set
$$N(K_1,K_2):=\{x\in \oR^d\mid (1,x)=Ye_0 \ \mbox{ for some } Y\in M(K_1,K_2)\}.$$
One can easily verify that
$$K_1\cap \{\pm 1\}^d \subseteq N(K_1,K_1)\subseteq N(K_1,K_2) \subseteq N(K_1,Q)\subseteq K_1.$$
Therefore, the choice $(K_1,K_2)=(K,K)$
provides the best relaxation $N(K,K)$ for $P$. However,
it is also interesting to consider the choice $(K_1,K_2)=(K,Q)$ giving
the weaker relaxation $N(K,Q)$
as it behaves better algorithmically.
Indeed, as observed in \cite{LS91},
if one can solve in polynomial time the (weak) separation problem over $K$,
then the same holds for $M(K,Q)$ and thus also for its projection
$N(K,Q)$; this
property holds for $N(K,K)$ under the more restrictive assumption that an explicit linear
description is known for $K$ whose size is polynomial (details will be given
later in this section).
One can obtain tighter relaxations for $P$ by iterating the constructions
$N(K,Q)$ and $N(K,K)$. One can iterate the construction $N(K,Q)$ by the sequence
$N(K,Q)$, $N(N(K,Q),Q)$, etc.
A first way in which the construction $N(K,K)$ can be iterated is by
considering the
sequence $N(K,K)$, $N(N(K,K),N(K,K))$, etc.
A major drawback is then that, even if $K$ is given by an explicit
linear system of polynomial length,
then it is not clear whether this holds for the next iterate
$N(K,K)$. A more tractable way is
to consider the sequence
$N(K,K)$, $N(N(K,K),K)$, etc.
For simplicity in the notation, for a polytope $H\subseteq K\subseteq Q$,
set
$$M(H):=M(H,Q),\ M'(H):=M(H,K),\ N(H):=N(H,Q),\ N'(H):=N(H,K).$$
The sequences $K,N(K,Q),N(N(K,Q),Q),\ldots$
and $K,N(K,K),N(N(K,K),K),\ldots$ can then be defined iteratively by
$$N^0(K)=(N')^0(K):=K,\ N^k(K):=N(N^{k-1}(K),Q), \ (N')^k(K):=N((N')^{k-1}(K),K)$$
for $k\ge 1.$
Thus $x\in \nu^k(K)$ if and only if
$(1,x)=Ye_0$ for some
$Y\in \mu(\nu^{k-1}(K))$ where $\mu=M$ (resp. $M'$) if $\nu=N$ (resp. $N'$).
One can reinforce the operators $N$ and $N'$ by adding positive semidefiniteness constraints.
For a polytope $H\subseteq Q$, define $M_+(H)$ (resp. $M'_+(H)$)
as the set of {\em positive semidefinite} matrices $Y\in M(H)$
(resp. $Y\in M'(H)$);
the projections $N_+(H)$ and $N'_+(H)$ and their iterates
are then defined in
the obvious way.
The following hierarchy holds:
\begin{equation}\label{relhierarchy}
P\subseteq N'_+(K)\subseteq N'(K)\subseteq N(K)\subseteq K, \
P\subseteq N'_+(K)\subseteq N_+(K)\subseteq N(K)\subseteq K.
\end{equation}
For membership in $M(K)$, condition (\ref{relii}) can be rewritten as
\begin{equation}\label{reliiN}
Y(e_0\pm e_i)\in \tilde K \ \mbox{ for } i=1,\ldots,d.
\end{equation}
As $Ye_0={1\over 2}(Y(e_0+e_i)+Y(e_0-e_i))$, we deduce that
\begin{equation}\label{relN}
N(K)\subseteq \conv(K\cap \{x\mid x_i=\pm 1\}) \ \mbox{ for any } i=1,\ldots,d.
\end{equation}
Using this fact and induction, one can prove
that after $d$ iterations
of the operator $N$ one finds the polytope $P$.
\begin{theorem}
\label{theoLS}
{{\rm \cite{LS91}} $N^d(K)=P$.}
\end{theorem}
\noindent
Obviously, the same holds for the operators $N_+$, $N'$ or $N_+'$ but the
corresponding sequences of relaxations
may converge faster to $P$.
% \begin{figure}[ht]
% \mbox{
% {\def\epsfsize#1#2{0.4#1}\epsfbox{diagram.eps}}}
%
%\label{hierarchy}
% \end{figure}
\medskip\noindent
{\bf Comparison with other lift and project methods.}
Other lift and project methods have been proposed in the literature, in particular,
by Balas, Ceria and Cornu\'ejols \cite{BCC93}, by
Sherali and Adams \cite{SA90} and, recently,
by Lasserre \cite{Las00,Las01b}.
Each of these methods produces a hierarchy of linear or
semidefinite (in the case of Lasserre) relaxations:
$P\subseteq K^d\subseteq \ldots \subseteq K^1\subseteq K$ such that
$P=K^d$.
For $k\ge 1$, the $k$-th iterate $S_k(K)$ in the Sherali-Adams hierarchy
is obtained by multiplying the system $Ax\ge b$ by each of the products
$\prod_{i\in I}(1+x_i)\prod_{j\in J}(1-x_j)$ for $I,J\subseteq [1,d]$ disjoint
with $|I\cup J|=k$ and, then, replacing each square $x_i^2$ by $1$,
linearizing each product $\prod_{i\in I}x_i$ and projecting back
on $\oR^d$; hence, the first step is identical to the first step of the Lov\'asz-Schrijver
method, i.e., $S_1(K)=N(K)$.
It is shown in \cite{LS91} that $S_t(K)\subseteq N^k(K)$ (see \cite{La01} for a simple proof).
The first relaxation $P_i(K)$ in the Balas-Ceria-Cornu\'ejols
hierarchy is obtained by multiplying $Ax\ge b$ by $1\pm x_i$ for some given $i\in [1,d]$
(and then linearizing and projecting back on $\oR^d$); the next
relaxations are defined iteratively by
$P_{i_1\ldots i_k}(K):=P_{i_k}(P_{i_1\ldots i_{k-1}}(K))$.
It is shown in \cite{BCC93} that
$P_{i_1\ldots i_k}(K)=\conv(K\cap\{x\mid x_{i_1},\ldots,x_{i_k}=\pm 1\})$.
Setting
\begin{equation}\label{relN0}
N_0(K):=\bigcap _{i=1}^dP_i(K)=\bigcap_{i=1}^d \conv(K\cap\{x\mid x_i=\pm 1\})
\end{equation}
we deduce from (\ref{relN}) that
\begin{equation}\label{relNN0}
N(K)\subseteq N_0(K)
\end{equation}
and, thus, $N^k(K)\subseteq N_0^k(K)=\bigcap_{i_1\ldots i_k}P_{i_1\ldots i_k}(K)$
for $k\ge 1$.
In fact, $N_0(K)$ can be seen as the `noncommutative'
analogue of $N(K)$ as $N_0(K)=\{x\in \oR^d\mid (1,x)=Ye_0 \ \mbox{ for some }
Y\in M_0(K)\}$ where
$M_0(K)$ is the set of matrices (not necessarily symmetric)
satisfying (\ref{reli}) and (\ref{reliiN}).
Using facts about moment sequences and representations
of positive polynomials as sums of squares,
Lasserre \cite{Las00,Las01b} introduces a new hierarchy
of semidefinite relaxations $Q_k(K)$ of $P$.
It is shown in \cite{La01} that it refines the Lov\'asz-Schrijver hierarchy; that is,
$Q_k(K)\subseteq N^k_+(K)$ and its relation to the Sherali-Adams
hierarchy is explained.
\medskip\noindent
{\bf Algorithmic aspects.}
Given a convex body $B\subseteq \oR^d$, the {\em separation problem}
for $B$ is the problem of deciding whether a given point $y\in \oR^d$ belongs to $B$ and, if not, of finding a hyperplane
separating $y$ from $B$; the {\em weak separation problem}
is the analogue problem where one allows for numerical errors. An important
application of the ellipsoid method is that, if one can solve in polynomial time the
weak separation problem for $B$, then one can optimize any linear objective
function over $B$ in polynomial time (with an arbitrary precision)
and vice versa.
(One should assume some technical information over $B$, like the knowledge of a ball contained in
$B$ and of a ball containing $B$.) See \cite{GLS88} for details.
An important property of the Lov\'asz-Schrijver construction is that,
if one can solve in polynomial time the weak
separation problem for $K$, then the same holds for $M(K)$ and $M_+(K)$ and, thus, for their projections
$N(K)$ and $N_+(K)$. Therefore, for any fixed $k$,
one can optimize in polynomial time a linear objective function
over the relaxations $N^k(K)$ and $N_+^k(K)$;
the same holds for the relaxations $S_k(K)$ and $P_{i_1\ldots i_k}(K)$ of Sherali-Adams and
of Balas-Ceria-Cornu\'ejols.
For the
operators $N'$ and $N'_+$ and for the Lasserre hierarchy, an analogue
result holds under the more restrictive assumption that an explicit linear description
is known for $K$ whose size is part of the input data.
\medskip\noindent
{\bf Identifying valid inequalities for $N(K)$ and $N_+(K)$.}
We mention two results from \cite{LS91}
permitting to construct inequalities valid for
$N(K)$ and
$N_+(K)$;
the first one follows directly from (\ref{relN}) and we prove the second one for completeness.
\begin{lemma}\label{lemvalid1}
Suppose that, for some $i=1,\ldots,d$, the inequality $a^Tx\ge \beta $
is valid for $K\cap \{x\mid x_i=\pm 1\}$, then the inequality
$a^Tx\ge \beta$ is valid for $P_i(K)$ and, thus, for
$N_0(K)$ and $N(K)$.
\qquad \end{lemma}
\begin{lemma}\label{lemvalid2}
Suppose that $a_i\ge 0$ for $i=1,\ldots,d$ and $\beta\le 0$.
If the inequality $a^Tx\ge \beta$ is valid for $K\cap\{x\mid x_i=-1\}$
for every $i$ for which $a_i>0$, then the inequality $a^Tx\ge \beta$
is valid for $N_+(K)$.
\end{lemma}
\begin{proof}
Set $b:=(-\beta,a)\in \oR^{d+1}$; thus $b\ge 0$. Let $Y\in M_+(K)$.
We show that $b^TYe_0\ge 0$. By the assumption, we know that
$b^TY(e_0-e_i) \ge 0$ if $a_i>0$.
Multiplying both sides of the inequality by $a_i$ and summing over $i=1,\ldots,d$
yields:
$$(\sum_{i=1}^da_i)b^TYe_0 \ge b^TY(\sum_{i=1}^d a_ie_i)=b^TY(b+\beta e_0)$$
and, thus, $(\sum_{i}a_i-\beta)b^TYe_0\ge b^TYb$.
The result now follows since $b^TYb\ge 0$ (as $Y$ is positive semidefinite) and
$\sum_ia_i-\beta>0$ (else, there is nothing to prove).
\qquad \end{proof}
\medskip\noindent
{\bf Comparing $N_+(K)$ with the basic semidefinite relaxation
in the equality case.}
The relaxation $N_+(K)$ is often stronger than some basic semidefinite relaxation
one can think of for the problem at hand; this is the case for the stable set problem and for max-cut (see later)
and, as we see now, when $K$ is defined by an equality system.
Suppose that $K=\{x\in \oR^d\mid Ax=b\}$. The set $\hat K$ consisting
of the vectors
$x\in \oR^d$ for which there exists a positive semidefinite matrix
$Y=\left(\matrix{1 & x^T\cr x & X}\right)$ satisfying $X_{ii}=1$ ($i=1,\ldots,d$)
and ${\rm Tr}(A^TAX)=b^Tb$, is a natural semidefinite
relaxation for $P$ which is contained in $K$.
(This relaxation can be obtained
by taking the dual of the Lagrange dual of the formulation:
$Ax=b$, $x_i^2=1$ ($i=1,\ldots,d$),
and $(Ax-b)^T(Ax-b)=0$; cf. \cite{PRW95},\cite{LO99}).
\begin{proposition}
$N_+(K)\subseteq \hat K.$
\end{proposition}
\begin{proof}
Let $x\in N_+(K)$ and $Y\in M_+(K)$ such that $(1,x)=Ye_0$.
Then, $Y(e_0\pm e_i)\in {\widetilde K}$ which means
that $Ax=b$ and $AXe_i=bx_i$ ($i=1,\ldots,d$) (setting $X:=(Y_{i,j})_{i,j=1}^d$).
Since $b=Ax=\sum_{i=1}^d (Ae_i)x_i$, then
${\rm Tr}(A^TAX)-b^Tb = \ds\sum_{i=1}^d (Ae_i)^TAXe_i -\ds \sum_{i=1}^d(Ae_i)^Tbx_i
= \ds\sum_{i=1}^d (Ae_i)^T(AXe_i-bx_i) =0$, implying
$x\in \hat K$.
\qquad \end{proof}
\section{The Cut Polytope and Some Relaxations}\label{secrelax}
\subsection{The cut polytope and the metric polytope}
Given an integer $n\ge 3$, set
$V_n:=\{1,\ldots,n\}$,
$E_n:=\{ij\mid 1\le i0$, the
inequality obtained from $a^Tx\ge \beta$ by anti-collapsing
nodes $u$ and $v$ is valid for
\\ $N_+^k(\MET(G\slash uv)$. \qquad
\end{proposition}
%\vspace*{-5mm}
It is obvious that $\CUT(K_n)$ is equal to the projection of $\CUT(K_{n+1})$
on the subspace $\oR^{E_n}$ indexed by the edge set of $K_n$; similarly for
$\MET(K_n)$. The same can be verified for $F_n$ and for any iterate
$\nu^k(\MET(K_n))$ (in the latter case, use Corollaries \ref{corYF}
and \ref{corsubgraph}).
\begin{proposition}\label{propsubgraph}
Let $G=(V_n,E)$ be a graph, $F\subseteq E$, and
$H:=(V_n,F)$ the corresponding subgraph of $G$.
Let $\nu$ be one of the operators $N,\ldots,N'_+$,
$\mu$ the associated operator from $M,\ldots,M'_+$ and let $k\ge 0$ be an integer.
If $Y\in \mu(\nu^k(\MET(G)))$, then its principal submatrix $X$ indexed by
the set $\{0\}\cup F$ belongs to
$\mu(\nu^k(\MET(H)))$.
\end{proposition}
\begin{proof}
It suffices to consider the case when $\nu=N,N'$ as $Y\succeq 0$ implies $X\succeq 0$.
We use the following facts in the proof:
$\MET(H)$ is the projection on $\oR^F$ of $\MET(G)$;
if $\xi$ belongs to the dual cone of $\MET(H)$, then its extension
$\xi':=(\xi,0,\ldots,0)\in \oR^E$ belongs to the dual of $\MET(G)$
and $X\xi $ is the projection
on $\oR^{\{0\}\cup F}$ of $Y\xi'$.
The proof is by induction on $k\ge 0$.
The case $k=0$ is obvious in view of the above observations.
Let $k\ge 1$ and suppose that the result holds for $k-1$.
Assume that $Y\in \mu(\nu^k(\MET(G)))$; we show that
$X\in \mu(\nu^k(\MET(H)))$. For this consider $\xi\in \MET(H)^*$ and
its extension $\xi'\in \MET(G)^*$. We show that
$x:=X\xi\in {\widetilde {\nu^k(\MET(H))}}$. By assumption,
$y:=Y\xi'\in {\widetilde {\nu^k(\MET(G))}}$.
Therefore, $y=Ae_0$ for some $A\in \mu(\nu^{k-1}(\MET(G)))$.
Using the induction assumption, the principal submatrix
$B$ of $A$ indexed by $\{0\}\cup F$ belongs to
$\mu(\nu^{k-1}(\MET(H)))$ and, thus,
$Be_0\in {\widetilde {\nu^k(\MET(H))}}$. Note now that
$x$ being the projection on $\oR^{\{0\}\cup F}$ of
$y$ is equal to $Be_0$.
This shows the result; indeed for $\nu=N$, restrict the above argument to
$\xi $ of the form $e_0\pm e_f$ ($f\in F$).
\qquad\end{proof}
%\vspace*{-5mm}
\begin{corollary}\label{corsubgraph}
Let $G=(V_n,E)$ be a graph, $H=(V_n,F)$ a subgraph of $G$,
$\pi_F$ the projection from $\oR^E$ onto $\oR^F$, $k\ge 0$ an integer and $\nu=N,\ldots,N'_+$.
Then, $\pi_F(\nu^k(\MET(G)))\subseteq \nu^k(\MET(H))$. In particular,
$\CUT(G)\subseteq \nu^k(G)\subseteq \nu^k(\MET(G))$. \qquad
\end{corollary}
%\vspace*{-1cm}
\subsection{Upper bound for the $N'$-index of a graph}\label{secboundN'}
We showed in Section \ref{secbound} the upper bound $n-4$ for the $N$-index of a graph on $n\ge 4$ nodes.
We will see in Section \ref{secvalidity} that
$$\eta_N(K_6)=\eta_{N_+}(K_6)=2,\ \eta_{N'}(K_6)=1,\
\eta_{N'_+}(K_n)\ge 2 \ \mbox{ for } n\ge 7.$$
Thus, $\eta_{N'}(G)\le 1$ for a graph on $n\le 6$ nodes.
Based on this fact, one can
show the slightly better upper bound $n-5$ for the $N'$-index of a graph
on $n\ge 6$ nodes.
\begin{theorem}
\label{theoindex}
Let $\nu$ be one of $N,\ldots,N'_+$
and let $h,k\ge 0$ be integers.
If there exist $k$ edges $e_1,\ldots,e_k$ in $G$
for which $\CUT(G\slash \{e_1,\ldots,e_k\})=\nu^h(\MET(G\slash \{e_1,\ldots,e_k\}))$,
then $\CUT(G)=\nu^{h+k}(\MET(G))$.
\end{theorem}
\begin{proof}
The proof is by induction on $k\ge 0$. The result holds trivially for $k=0$.
Let $k\ge 1$ and suppose that the result holds for $k-1$.
Let $a^Tx\ge \beta$ be an inequality valid for $\CUT(G)$.
By Lemma \ref{lemmabasic2}, the inequalities
obtained from it by collapsing and anti-collapsing the end nodes
of $e_k$ are valid for $\CUT(G\slash e_k)$ which is equal to
$\nu^{h+k-1}(\MET(G\slash e_k))$ by
the induction assumption.
By Proposition \ref{propvalid1}, this implies that
$a^Tx\ge \beta$ is valid for $\nu^{h+k}(\MET(G))$.
\qquad\end{proof}
%\vspace*{-5mm}
\begin{corollary}\label{corN'}
The $N'$-index of a graph on $n\ge 6$ nodes is at
most $n-5$.\end{corollary}
\begin{proof}
If $G$ is connected, one can find a set $F$ of $n-6$ edges whose contraction produces
a graph on six nodes; as $\CUT(G\slash F)=N'(\MET(G\slash F))$,
we deduce from Theorem \ref{theoindex} that
$\CUT(G)=(N')^{|F|+1}(\MET(G))=(N')^{n-5}(\MET(G))$.
If $G$ is not connected, then by the above
$\CUT(G_i)=(N')^{n-5}(\MET(G_i))$ for each connected component $G_i$ of $G$;
using Proposition \ref{propcliquesum} this implies that
$\CUT(G)=(N')^{n-5}(\MET(G))$.
\qquad\end{proof}
%\vspace*{-1cm}
\subsection{Behaviour of the index under taking graph minors and clique sums}
\label{secminor}
An important motivation for the study of the LS relaxations is that one can
solve the max-cut problem in polynomial time over the class of graphs
having bounded $\nu$-index ($\nu=N,N_+$) or bounded projected
$\nu$-index ($\nu=N,\ldots,N'_+$). It is therefore of great interest
to understand which are the graphs having small index, e.g., $\le 1$.
This is however a difficult question.
As a first step, we study here
whether these graph classes are closed under taking minors and clique sums.
Let $G=(V_n,E)$ be a graph with edge set $E\subseteq E_n$.
Given an edge $e=uv\in E$, recall that $G\backslash e$ is the graph obtained from $G$ by {\em deleting} edge $e$ and
$G\slash e$ is the graph obtained from $G$ by contracting $e$;
a {\em minor} of $G$ is then a graph obtained from $G$ by a sequence of deletions and/or contractions.
Let $G_i(V_i,E_i)$ ($i=1,2$)
be two graphs such that the set $V_1\cap V_2$ induces a clique in both $G_1$ and $G_2$.
Then, the graph $G:=(V_1\cup V_2,E_1\cup E_2)$ is called the {\em clique $t$-sum}
of $G_1$ and $G_2$, where $t:=|V_1\cap V_2|$.
\begin{proposition}\label{propminor}
For $\nu=N,\ldots,N'_+$,
$\eta^\pi_\nu(H)\le \eta^\pi_\nu(G)$ if $H$ is a minor of $G$ and
$\eta_\nu(H)\le \eta_\nu(G)$ if $H$ is a contraction minor of $G$.
\end{proposition}
\begin{proof}
Monotonicity of the projected index under taking deletion minors
follows directly from the definitions.
Suppose now that $H$ is a contraction minor of $G$; say,
$G=(V_n,E)$, $e:=uv\in E$,
and $H=G\slash uv =(V_n\setminus \{u,v\}\cup\{w\},F)$.
We show that $\eta_\nu(H)\le \eta_\nu(G)$. For this, suppose that
$\CUT(G)=\nu^k(\MET(G))$; we show that $\CUT(H)= \nu^k(\MET(H))$.
Let $x\in \widetilde {\nu^k(\MET(H))}$;
then $x=Xe_0$ for some $X\in \mu(\nu^{k-1}(\MET(H)))$. By Proposition \ref{propYF}, the 1-extension $Y$ of $X$ belongs to
$\mu(\nu^{k-1}(\MET(G)))$ and $Y_{0,0}=Y_{0,uv}$. Thus, $y:=Ye_0\in
\widetilde{\nu^k(\MET(G))}=\widetilde{\CUT(G)}$.
By Lemma \ref{lemmabasic1} (ii), this implies that $x=y^{F,1}\in \widetilde{\CUT(H)}$.
We now show that $\eta_\nu^\pi(H)\le \eta_N^\pi(G)$.
Suppose that $\CUT(G)=\nu^k(G)$; we show that $\CUT(H)=\nu^k(H)$.
For this, let $x\in \nu^k(H)$. Thus, $x=\pi_F(Xe_0)$
for some $X\in \mu(\nu^{k-1}(\MET(K_{n-1})))$ with $X_{0,0}=1$. Viewing
$K_{n-1}$ as $K_n\slash uv$, we have from Proposition \ref{propYF}
that the 1-extension $Y$ of $X$ belongs to $\mu(\nu^{k-1}(\MET(K_n)))$ and
$Y_{0,0}=Y_{0,uv}=1$.
Thus, $y:=\pi_E(Ye_0)\in \nu^k(G)=\CUT(G)$, implying
$x=y^{F,1}\in \CUT(H)$.
\qquad\end{proof}
%\vspace*{-5mm}
\begin{proposition}\label{propcliquesum}
Let $G$ be the clique $t$-sum of two graphs $G_1$ and $G_2$ where $t=0,1,2,3$.
Then,
$\eta^\pi_\nu(G)\le \max(\eta^\pi_\nu(G_1),\eta^\pi_\nu(G_2))$ and
$\eta_\nu(G)\le \max(\eta_\nu(G_1),\eta_\nu(G_2))$.
\end{proposition}
\begin{proof}
Let $G=(V_n,E)$ be the clique $t$-sum of two graphs $G_i=(V_i,E_i)$
for $i=1,2$ with $t\le 3$; thus $V_n=V_1\cup V_2$ and $E=E_1\cup E_2$.
We use
the following fact shown in \cite{Ba83}:
Given $y\in \oR^{E_1\cup E_2}$ and its projections $y_i:=(y(e))_{e\in E_i}$ for $i=1,2$,
then $y\in \CUT(G)\Longleftrightarrow y_i\in \CUT(G_i)$ for $i=1,2$.
Let $k\ge 0$ be an integer.
Suppose first that $\CUT(G_i)=\nu^k(G_i)$ for $i=1,2$ and let $y\in
\nu^k(G)$; we show that $y\in \CUT(G)$. For this it suffices to show
that $y_i\in \nu^k(G_i)$ for $i=1,2$.
There exists $Y\in \mu(\nu^{k-1}(\MET(K_n)))$ such that $y=\pi_E(Ye_0)$.
By Proposition \ref{propsubgraph} the principal submatrix $Y_i$ of $Y$ indexed
by $\{0\}\cup F_i$ where $F_i$ is the edge set of the complete graph
on $V_i$, belongs to $\mu(\nu^{k-1}(\MET(K_{V_i})))$.
Thus, $y_i=\pi_{E_i}(Y_ie_0)\in \nu^k(G_i)$ for $i=1,2$.
Suppose now that $\CUT(G_i)=\nu^k(\MET(G_i))$ for $i=1,2$ and let $y\in
{\widetilde {\nu^k(\MET(G))}}$;
we show that $y_i\in {\widetilde {\nu^k(\MET(G_i))}}$.
There exists $Y\in \mu(\nu^{k-1}(\MET(G)))$ such that $y=Ye_0$. By
Proposition \ref{propsubgraph} the principal
submatrix $Y_i$ of $Y$ indexed by $\{0\}\cup E_i$ belongs to
$\mu(\nu^{k-1}(\MET(G_i)))$ and, thus, $y_i=Y_ie_0\in
{\widetilde{\nu^k(\MET(G_i))}}$.
\qquad\end{proof}
As the class of graphs $G$ with $\eta^\pi_\nu(G)\le 1$
is closed under taking minors, we know from
the theory of Robertson and Seymour \cite{RS} that there exists a finite list
of
{\em minimal forbidden minors} characterizing membership in it;
that is, $\eta^\pi_\nu(G)\le 1$ if and only if $G$ does not contain any member
of the list as a minor.
For $\nu=N,N_+$, $\eta^\pi_\nu(K_6\backslash e)=1$ while $\eta^\pi_\nu(K_6)=2$;
hence the graph $K_6$ is a minimal forbidden minor for both properties $\eta^\pi_N(G)\le 1$ and $\eta^\pi_{N_+}(G)\le 1$.
There are necessarily other minimal forbidden minors.
Indeed, the max-cut problem is known to be NP-hard for the class of graphs having
no $K_6$-minor (in fact, also for the class of apex graphs;
that is, the graphs having a node whose deletion results in a planar
graph) (cf. \cite{Ba82}).
Let $G_0$ denote the graph obtained from $K_7$ by removing a matching of size 3. We
have verified that, for a graph $G$ on 7 nodes distinct from
$G_0$, $\eta^\pi_N(G)\le 1$
if and only if it does not contain $K_6$ as a minor.
It would be interesting to compute $\eta^\pi_N(G_0)$; if its value
is $\ge 2$ then $G_0$ is
another minimal forbidden minor.
\medskip
In view of Propositions \ref{propminor} and \ref{propcliquesum},
the property $\nu^\pi_\nu(G)\le 1$
is preserved under the $\Delta Y$ operation
(which consists of replacing a triangle by a claw $K_{1,3}$). However
it is not preserved under the converse $Y\Delta$ operation.
Indeed, if $G$ is the graph obtained from $K_6$ by applying
one $\Delta Y$ transformation, then
$\eta_N(G)=\eta_N^\pi(G) =1$ (by (\ref{alpha}))
while $\eta_N(K_6)=2$.
We have verified that all the graphs in the Petersen family
(consisting of the graphs that can be obtained from $K_6$ by $Y\Delta$ and $\Delta Y$ transformations) except $K_6$
have projected $N$-index equal to 1.
\section{Valid Inequalities for the New Relaxations}\label{secvalidity}
We saw above that the $N$-index of $K_n$ is at most $n-4$, with equality
for $n=4,5$.
We conjecture that equality holds for any $n$.
In order to show this conjecture,
one has to find an inequality valid for $\CUT(K_n)$ which is not valid
for $N^{n-5}(K_n)$. A possible candidate is the inequality
\begin{equation}\label{ine1}
\displaystyle\sum_{1\le i