

		%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
		%%  Below is our abstract in latex   %%
		%%  Any communication regarding the  %%
		%%  abstract should be sent to       %%
		%%  Mark Goldberg                    %%
		%%  Department of Computer Science   %%
		%%  Rensselaer                       %%
		%%  Troy, NY 12181                   %%
		%%  email: goldberg@cs.rpi.edu       %%
		%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\documentstyle[12pt]{article}      
%\newtheorem
\setlength{\oddsidemargin}{10pt}
\setlength{\evensidemargin}{10pt}
\setlength{\marginparwidth}{0pt}
\setlength{\marginparsep}{0pt}
\setlength{\topmargin}{-40pt}
\setlength{\textwidth}{450pt}
\setlength{\textheight}{630pt}
\setlength{\tabbingsep}{0pt}
\setlength{\headsep}{30pt}
\setlength{\fboxsep}{40pt}
\setlength{\fboxrule}{4pt}
\setlength{\footnotesep}{15pt}
\setlength{\parindent}{24pt}   
\setlength{\parskip}{8pt plus 5pt}
%This is the end of the header information.   
\newcommand{\mysect}[1]{\section{\protect \normalsize\protect \bf #1}}
\newcommand{\mysubsect}[1]{\subsection{\protect \rm \protect \normalsize #1}}
\newcommand{\cA}{{\cal A}}
\newcommand{\cB}{{\cal B}}
\newcommand{\cC}{{\cal C}}
\newcommand{\cD}{{\cal D}}
\newcommand{\cE}{{\cal E}}
\newcommand{\cF}{{\cal F}}
\newcommand{\cG}{{\cal G}}
\newcommand{\cH}{{\cal H}}
\newcommand{\cI}{{\cal I}}
\newcommand{\cJ}{{\cal J}}
\newcommand{\cK}{{\cal K}}
\newcommand{\cL}{{\cal L}}
\newcommand{\cR}{{\cal R}}
\newcommand{\cS}{{\cal S}}
\newcommand{\cP}{{\cal P}}
\newcommand{\cT}{{\cal T}}
\def\Indent{\hspace*{\parindent}}
\newcommand{\defeq}{{=_{\mbox{\tiny def}}}}
\begin{document}

\title{\large \bf Maximum Cliques in a Graph\\[5pt]
\normalsize \it submitted to the\\
$2^{nd}$ DIMACS Algorithm Implementation Challenge}
\author{\large Mark K. Goldberg, Reid Rivenburgh}
\date {Rensselaer Polytechnic Institute}
\maketitle
\begin{abstract}
A restricted backtracking algorithmic paradigm is applied to the Maximum 
Clique Problem. The notion of backtracking coordinates is introduced. 
The program searches for the cliques whose backtracking coordinates are
bounded by the values given in the input.
\end{abstract}

\noindent
{\bf Introduction} \\[9pt]
We used a variation of the standard backtracking algorithmic paradigm to create 
an efficient C-program for constructing a clique in a graph.
The program was tested on randomly generated graphs with up to 1000 vertices.
If $Z_{n,p}$ denotes 
the maximum size of a clique in a random graph with $n$ vertices and edge 
probability $p$, then (see \cite{BE,Ma}) for the threshold function 
$z(n,p) = 2 \log_{1/p} n - 2 \log_{1/p} \log_{1/p} n + 
2 \log_{1/p} (e/2) + 1$ and any $\epsilon >0$, the following 
holds true:
$$\lim_{n \rightarrow \infty}Prob \{\lfloor z(n,p)\rfloor - 1 -\epsilon
\leq Z_{n,p} \leq \lfloor z(n,p)\rfloor +\epsilon \} = 1.$$

The table below presents our results for $n=1000$ and 
$p= 0.3,~0.4,~ 0.5,~0.6,~0.7$ and $0.8$ with 
the corresponding values of $z(n,p)$ in the second row. 
Every entry of the third row is the average over 100 random graphs with 
the respective parameters. All experiments were run on a  SPARC system
600 (Sun 4/600); the entries of the fourth row are the average running times
in seconds per individual runs. The value of the second column in the
third row was obtained by running the program in the exhaustive search mode;
the other  values of the third row were obtained when the program was run
in the heuristic mode.

\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|} \hline
$p=$&0.3 & 0.4 & 0.5 & 0.6 & 0.7& 0.8 \\\hline
theory&10.08 &12.34 & 15.18 & 19.05 & 24.83&34.84 \\\hline
program&9.44&11.98 &14.97 &18.78 &25.00&35.70 \\\hline
run time&360&530&1910&1660&1220& 810\\\hline
\end{tabular}
\end{center}


\noindent
{\bf Backtracking} \\[9pt]
The backtracking algorithmic paradigm is usually described as ``walking''
along a (virtual) backtracking tree. In our implementation,
the backtracking tree  of the Maximum Clique problem is a directed rooted tree 
whose nodes are labeled by lists of vertices of the graph and whose edges 
are labeled by individual vertices, so that
\begin{itemize}
\item the label $L_0=\{v_0, v_1,\ldots,v_{n-1}\}$ of the root 
comprises all vertices of the graph;
\item if a node $z$ has a non-empty label $L'=\{u_0,\ldots,u_{k-1}\}$, 
then the children nodes of $z$ are formed as follows:
\begin{itemize}
\item apply a reordering procedure to obtain a new list 
$L''= \{w_0,\ldots, w_{k-1}\}$;
\item  for each $ i~(0\leq i<k-1)$, construct a new list 
$M_i$ comprised of the vertices $w_j$ in $L''$ with indices $j>i$ 
that are adjacent to $w_i$; label the child node $z_i$ of $z$ by $M_i$ and 
the directed edge $(z,z_i)$ of the tree by $w_i$.
\end{itemize}
\end{itemize}
Thus, the leaves of the backtracking tree correspond to maximal cliques;
the cliques can be retrieved by tracing the labels of the path leading from the
root to the leaf. Simple pruning can be applied to reduce the number of
nodes visited.  In our implementation, the size of the currently largest 
clique is compared with some easily computable upper bound on the size of 
the clique which could be constructed if the node in question were fully explored. 

If the procedure is implemented carefully, the program  is
useful for small and/or sparse graphs.
For example,  when our program is requested to execute an exhaustive search,
it spends on average 0.31 sec to find a maximum clique in a randomly generated 
graph with $n=100$ vertices and edge probability $p =0.5$; if  $n= 200$ 
and $p= 0.5$, the running time on average is  $9.25$ seconds. 
For $n= 1000$ and $p= 0.3$ (resp. 0.4), the average time is 360 
(resp.  13,100) seconds. 

\noindent
{\bf Bounds} \\[9pt]
If the reordering procedures used by the algorithm are fixed, then every
leaf of the backtracking tree can be uniquely described by the integer
vector $(l_0,l_1,\ldots,l_{r-1})$ ($r$ is the size of the 
corresponding clique) defined as follows.
If $(z_0,z_1,\ldots,z_r)$ is the sequence of the tree nodes
of the path connecting the root $z_0$ with a leaf 
$z= z_r$ and $s_i$ is the label of the edge $(z_i,z_{i+1})$,  then $l_i$ is 
the index of $s_i$ in the list which serves as the label for $z_i$ 
$(i=0,\ldots,r-1)$.
We call $(l_0,\ldots,l_{r-1})$ the {\it backtracking coordinates} of the
clique.

Obviously, the vector $(0,0,\ldots,0)$ corresponds to the clique
obtained by applying the greedy\footnote{We assume that the reordering
procedures are ``simple'', certainly of polynomial complexity; in our
experiments the reorderings used were always linear or quadratic;
this justifies using the word ``greedy''.} algorithm. In general, it is 
interesting to consider a restriction of the full backtracking algorithm 
for which the only  nodes visited are those whose backtracking
coordinates satisfy some ``bounding'' conditions; for example, the
nodes whose backtracking coordinates are bounded by a given constant $B$. 
Since the running time of the program increases exponentially with $B$,
the question is what the smallest value of $B$ is which would guarantee
that the program finds a maximum or near maximum clique in  every (or
almost every) graph in a given class of graphs. We experimentally found 
that such a value of $B$ is surprisingly small for randomly generated graphs.
A more general question is, given a class of graphs, how the accuracy of 
the solution depends on $B$ (for all or for most of the graphs). 
In our experiments, we used individual bounds for every level of the 
backtracking tree. The experiments showed that only the few  first bounds 
need to be positive to achieve an optimal or close to optimal solution.
The input to our program includes the values of $n$ and $p$, an upper bound on
the maximum clique size, and the bounds on the backtracking coordinates.
Thus, depending on the input, the search executed by the program ranges
from greedy to exhaustive.

\noindent
{\bf Goals}

\noindent
Our main goal is  to find out if there is a pattern to the backtracking
coordinates of the maximum cliques in graphs from different classes. 
The classes of initial interest are random graphs with different densities, 
random regular graphs, and graphs of different combinatorial structures.
The latter include the graphs that come from the {\it coloring problem}.
It is well known that coloring the vertices of a given graph $G(V,E)$ 
in a given number of $k$ colors is equivalent to constructing a maximum 
independent set in an auxiliary graph $\cC_k(X,F_1 \cup F_2)$ defined by
\begin{itemize} 
\item $X \defeq	\{(v,i)|~v \in V;~ i = 0,\ldots,k-1\};$ 
\item $F_1\defeq \{((v,i),(v,j))~|~v\in V,~i,j=0,\ldots,k-1~(i\not = j);\}$
\item $F_2 \defeq \{((v,i), (u,i))~|~(v,u) \in E,  i=0,\ldots,k-1\}$;
\end{itemize}
Another class of graphs we will be investigating comes from the {\it packing
problem}. Given $t,k,v (1 \leq t \leq k \leq v)$, the problem is to find
the largest number, $D(v,k,t)$, of $k$-subsets of $\{1,2,\ldots ,v\}$ such
that every two of them intersect in fewer than $t$ elements.
It is easy to see that the packing problem is one of finding
a maximum independent set in a graph $\cP(v,k,t)$  whose vertices are
the $k$-subsets of a $v$-set, and two vertices are adjacent if
their intersection contains at least $t$ elements.

If the values of the initial parameters are not very small, the sizes of
graphs $\cC_k$ and especially $\cP(v,k,t)$ are prohibitively large, making it 
impossible to experiment with their implicit representations.
It would still be possible to investigate optimal backtracking coordinates 
of maximal independent sets for such graphs even for not-too-small 
values of the 
parameters. For this reason, it will be necessary to use and further develop 
the machinery of symbolic set manipulation from \cite{BG}.

\begin{thebibliography}{99}
\bibitem{BG} D. Berque, R. Cecchini, M. Goldberg, R. Rivenburgh,
The {\it SetPlayer} System for Symbolic Computation on Power Sets, to
appear in {\it J. of Symbolic Computation}.

\bibitem{BE} B. Bollob\'as and P. Erd\"os, Cliques in Random Graphs,
{\it Mathematical Proceedings of the Cambridge Philosophical Society},
Vol 80,  (1976) pp. 419--427.

\bibitem{Ma} D. Matula, The Largest Clique Size in a Random Graph, 
Southern Methodist University, Tech. Report, CS 7608 (April 1976).
\end{thebibliography}
\end{document}

