%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% 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 ii$ 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}