%Farid Alizadeh
%ICSI
%1947 Center Street, suit 600
%Berkeley CA 94706-1105
%e-mail: alizadeh@icsi.berkeley.edu

\documentstyle{article}
\newcommand{\trace}{{\rm trace} \:}
\newcommand{\zup}{\overline{z}}
\newcommand{\zdown}{\underline{z}}
\newcommand{\phiup}{\overline{\phi}}
\newcommand{\phidown}{\underline{\phi}}
\newcommand{\Xhalf}{X^{1/2}}
\newcommand{\Xnhalf}{X^{-1/2}}
\newcommand{\VEC}{{\bf vec}}
\newcommand{\MAT}{{\rm Mat}}
\newcommand{\SRN}{{\Re^{\frac{n\times n}{2}}}}
\begin{document}
\title{Lov\'asz Number of Graphs and Cliques}
\author{Farid Alizadeh\thanks{International Computer Science Institute,
1947 Center Street, Berkeley CA 94706. {\bf e-mail}:
alizadeh@icsi.berkeley.edu}}
\maketitle

This abstract presents a proposal for computing weighted maximum cliques 
(or maximum
independent sets) of undirected graphs. The main idea is to use Lov\'asz
number of graphs as an upper bound in a branch and bound technique.
Let $G=(V, E, {\bf w})$ be a weighted graph with $|V|=n$ and $|E|=m$ 
and ${\bf w}\in\Re^n$ a
weight vector on the vertices of the graph. We assume that $w_i\geq 0$
since otherwise, one may simply delete a vertex of negative weight. Let
$\omega(G, {\bf w})$ and $\chi(G, {\bf w})$ be, respectively, the weighted
clique number and the weighted chromatic number of graph $G$. (The
unweighted case corresponds to ${\bf w}={\bf 1}$ the vector of all ones.
In that case, we write $\omega(G)$ and $\chi(G)$.) Lov\'asz
\cite{lov-79}
introduced the following invariant of graphs which we refer to as the
Lov\'asz number of graphs $\theta(G,{\bf w})$. Let $\cal M$ be a set of
matrices $X\in\SRN$ whose $i,j$ entries are zero whenever $i=j$ or $i,j$
is an edge in $G$. Thus $\cal M$ is an affine set of $n\times n$ matrices
of dimension $n(n-1)/2-m$. Let $\lambda_1(X)$ be the largest eigenvalue
of the symmetric matrix $X$. Then
\begin{equation}\label{theta}
\theta(G,{\bf w}):=\min_{X\in {\cal M}}\lambda_1(X+W)
\end{equation}
where $W$ is the rank one matrix obtained by multiplying ${\bf w}$ by
itself: $W:={\bf w}{\bf w}^T$.

Two key results are known about the invariant $\theta$. First,
\[
\omega(G, {\bf w}) \leq \theta(G, {\bf w}) \leq \chi(G, {\bf w})
\]

So, $\theta$ is simultaneously an upper bound for the clique number and
chromatic number of graphs. The second key result is that $\theta$ is
polynomial time computable. In fact, the minimization problem in the
definition \ref{theta} is a convex optimization problem.
Gr\"otschel, Lov\'asz and Schrijver in \cite{GLS-88} show that one can use 
the ellipsoid method to compute $\theta$ 
up to any prescribed accuracy. (Note that
$\theta$ is not necessarily rational, however it is algebraic.) We have
previously shown that, at least theoretically, one can use a better
algorithm to compute $\theta$ \cite{ali-91a}, \cite{ali-91b} and
\cite{ali-91d}. The method used there is an extension of interior point
methods for linear programming. More specifically, \ref{theta} may be
formulated as the following optimization problem:
\begin{equation}\label{dual}
\begin{array}{lll}
\min & z & \\
\mbox{subject to}& zI +X + W \succeq 0 & \\
& X_{ij}=0& \mbox{for all }i=j\mbox{ or }ij\in E
\end{array}
\end{equation}
This optimization problem is quite similar to linear programming with the
difference that instead of the ``component--wise'' inequalities $\geq$ we
have the so--called {\em L\"owner} inequality $\succeq$. For two
symmetric $n\times n$ matrices $A$ and $B$, $A\succeq B$ if and only if
$A-B$ is positive semi-definite. Since the cone of positive semi-definite
matrices is convex the optimization problem \ref{dual} is a convex
optimization problem. In addition, there is a dual equivalent of
\ref{dual} which may be obtained similar to the way duals are obtained in
linear programs:
\begin{equation}\label{primal}
\begin{array}{lll}
\max & W\bullet Y & \\
\mbox{subject to}& \trace Y =1 & \\
 & Y_{ij}=0 & \mbox{for all }ij\not\in E\\
& Y\succeq 0 &
\end{array}
\end{equation}
where $A\bullet B$ is the inner product of matrices:
\[
A\bullet B:=\sum_{i,j} A_{ij}B_{ij}=\trace(A^TB)
\]
Furthermore, a ``complementary slackness'' property holds which
states that $X^*$ is optimal solution for \ref{dual} and $Y^*$ is optimal
solution for \ref{primal} if and only if
\[
Y^*(\lambda_1(X^*)I-X^*-W)=0
\]

These relations allow us to estimate the Lov\'asz number as accurately as
possible. However, we only need to compute $\lfloor \theta\rfloor$.
Since, for $X$ and $z$ feasible for \ref{dual} and $Y$ feasible for
\ref{primal} the quantity $Y\bullet(zI-X-W)$ represents the ``duality gap'' we
only need to find $X$, $z$ and $Y$ such that $Y\bullet(zI-X-W)<1$. 

It turns out that  for problem \ref{primal} if we add the integrality
condition to entries of $nY$, then the solution is exactly the maximum
clique problem \cite{LS-91}. In that case the diagonal of optimal
integral $Y$ is precisely $n$ times the characteristic vector of a maximum 
clique.
So \ref{primal} is a ``nonlinear''
relaxation of the maximum clique problem. In classical branch and bound
theory it is customary to use linear programming relaxation of
the combinatorial optimization problem under consideration. In general, 
however, if one can
derive nonlinear relaxations that are still easy to optimize over, then
one may be able to obtain sharper bounds than are possible with linear
programming relaxations. Lov\'asz's bound is one example of such
nonlinear relaxation for the maximum clique problem. Our proposal is to
implement this branch and bound technique using an efficient interior
point algorithm to compute the bound.

In light of recent results \cite{ALMSS-92a} it is impossible to find bounds 
that estimate the maximum clique to within $n^\epsilon$ for some constant
$\epsilon$. However the following probabilistic results are known. In a
random graph where each edge exists with probability $p$, the expected
size of maximum clique is approximately $\log n/\log(1/p)$  (see
\cite{Bol-85}) while the expected value of $\theta$ is approximately
$C\sqrt{nq/p}$, where $q=1-p$ and $C$ is some constant between 1/2 and 2, 
(see \cite{Juh-82}). However, to our knowledge, the expected value of
$\omega(G)/\theta(G)$ is unknown!

Roughly speaking, the branch and bound approach works as follows. First,
problem \ref{primal} and \ref{dual} are solved (using a primal--dual interior
point method developed in \cite{ali-91d}) If it happens that the diagonal
of $Y^*$ is a 0-1 vector then we have the clique. If not we start with
one nonintegral entry and branch the process into two subproblems: one
with that entry set at 1 and the other with that entry set at zero. We
then inductively proceed to solve each subproblem separately. The key
point is that we do not branch on those subproblems whose relaxation
value (i.e the corresponding $\theta$ value ) is smaller than the partial
cliques obtained so far.

{
\lineskip 3pt
\newcommand{\etalchar}[1]{$^{#1}$}
\begin{thebibliography}{ALM{\etalchar{+}}92}

\bibitem[Ali91a]{ali-91b}
F.~Alizadeh.
\newblock {\em Combinatorial Optimization with Interior Point Methods and
  Semi-Definite Matrices}.
\newblock PhD thesis, University of Minnesota, Minneapolis, Minnesota, 1991.

\bibitem[Ali91b]{ali-91a}
F.~Alizadeh.
\newblock A sublinear-time randomized parallel algorithm for the maximum clique
  problem in perfect graphs.
\newblock In {\em Proc. 2nd ACM-SIAM Symposium on Discrete Algorithms}, 1991.

\bibitem[Ali92]{ali-91d}
F.~Alizadeh.
\newblock Combinatorial optimization with semi-definite matrices.
\newblock In {\em proceedings of the second Integer Programming and
  Combinatorial Optimization (IPCO) conference}. Carnegie--Mellon University,
  1992.

\bibitem[ALM{\etalchar{+}}92]{ALMSS-92a}
Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy.
\newblock Proof verification and hardness of approximation problems.
\newblock In {\em Proc. 33rd IEEE Annual Symposium on Foundations of Computer
  Science}, pages 14--23, 1992.

\bibitem[Bol85]{Bol-85}
Bella Bollobas.
\newblock {\em Random Graphs}.
\newblock Academic Press, 1985.

\bibitem[GLS88]{GLS-88}
M.~Gr{\"{o}}tschel, L.~Lov\'{a}sz, and A.~Schrijver.
\newblock {\em {Geometric Algorithms and Combinatorial Optimization}}.
\newblock Springer Verlag, 1988.

\bibitem[Juh82]{Juh-82}
Ferenc Juh\'{a}sz.
\newblock The asymptotic behavior of lov\'{a}sz's {$\vartheta$} function for
  random graphs.
\newblock {\em Combinatorica}, 2(2):153--155, 1982.

\bibitem[Lov79]{lov-79}
L.~Lov\'{a}sz.
\newblock On the shannon capacity of a graph.
\newblock {\em IEEE Trans. Info. Theory}, 25(1), January 1979.

\bibitem[LS91]{LS-91}
L.~Lov\'{a}sz and A.~Schrijver.
\newblock {Cones of Matrices and Setfunctions, and 0-1 Optimization}.
\newblock {\em SIAM J. Optimization}, 1(2), 1991.

\end{thebibliography}
}

\end{document}