% Pardalos et al (test clique problems) % Submitted to teh Journal of Global Optimization \documentstyle[12pt]{article} \renewcommand{\baselinestretch}{1.2} \textwidth 16cm \textheight 23cm \topmargin -0.9in \evensidemargin 0.00in \oddsidemargin 0.00in \newtheorem{Theorem}{Theorem} \newtheorem{Corollary}{Corollary} \newtheorem{Lemma}{Lemma} \newtheorem{Definition}{Definition} \newtheorem{Property}{Property} \newtheorem{Proposition}{Proposition} \newtheorem{example}{Example} \begin{document} \title{Test Case Generators and Computational Results for the Maximum Clique Problem.} \author{Jonas Hasselberg \\ Royal Institute of Technology \\ Department of Computer Science \\ KTH, Stockholm, Sweden \\ \\ Panos M. Pardalos and George Vairaktarakis \\ Department of Industrial and Systems Engineering, \\ University of Florida, Gainesville FL, 32611.} \date{} \maketitle \begin{abstract} In the last years many algorithms have been proposed for solving the maximum clique problem. Most of these algorithms have been tested on randomly generated graphs. In this paper we present different test problem generators that arise from a variety of practical applications, as well as graphs with known maximum cliques. In addition, we provide computational experience with two exact algorithms using the generated test problems. \end{abstract} \section{Introduction} Let $G = (V,E)$ be an undirected graph where $V = \{v_{1},v_{2},\ldots,v_{n}\}$ is the set of vertices in $G$, and $E\subseteq V\times V$ is the set of edges in $V$. Throughout the paper we denote the size of a set $V$ by $|V|$. The adjacency matrix of $G$ is denoted by $A_{G} = (a_{ij})_{n\times n}$ where $a_{ij} = 1$ if $(i,j)\in E$, and $a_{ij} = 0$ if $(i,j)\not\in E$. The complement graph of $G = (V,E)$ is denoted by $\overline{G} = (V,\overline{E})$, where $\overline{E} = \{(i,j)|i,j \in V, i \neq j\ {\rm and}\ (i,j)\not\in E\}$. For a subset $S\subseteq V$ we call $G(S) = (S,E \cap (S \times S))$ the subgraph induced by $S$. A graph $G = (V,E)$ is complete if and only if $\forall\, i,j\in V,\ (i,j)\in E$. A {\em clique} $C$ is a subset of $V$ such that the induced graph $G(C)$ is complete. The maximum clique problem is to find a clique $C$ of maximum cardinality in a graph $G$. A {\em vertex cover} $S$ is a subset of $V$ such that every edge $(i,j)\in E$ is incident to at least one vertex in $S$. The minimum vertex cover problem is to find a vertex cover of minimum cardinality in the graph $G$. An {\em independent set} ({\em stable set}, {\em vertex packing}) is a subset of $V$, whose elements are pairwise non-adjacent. The maximum independent set problem is to find an independent set of maximum cardinality. It is easy to see that $S$ is a clique in a graph $G = (V,E)$ if and only if $V-S$ is a vertex cover in the complement graph $\overline{G} = (V,\overline{E})$, and if and only if $S$ is an independent set of $\overline{G}$. Thus, the maximum clique problem, the vertex cover problem and the maximum independent set problem are equivalent. In addition, they are all $\cal N$$\cal P$-complete, which means that unless $\cal P$= $\cal N$$\cal P$ there exists no algorithm that can solve either problem in time polynomial to the size of the problem. For more details about the maximum clique problem refer to \cite{BX,BY,CP,PR,X} and the recent survey \cite{PX} which presents results concerning algorithms, complexity and applications. The survey also provides an up to date bibliography on the maximum clique problem. In many applications, the underline problem can be formulated as a maximum clique problem while in others a subproblem of the solution procedure consists of finding a maximum clique. This necessitates the development of fast exact and approximate algorithms for the problem. Most of the proposed exact and heuristic algorithms have been tested on randomly generated graphs. In this paper we present different test problem generators that arise from a variety of practical applications, as well as graphs with known maximum clique. The application areas considered in this paper are diverse. For example, we will present a class of graphs from which we can prove or disprove Keller's conjecture; a famous problem in geometry, a part of which is still open. Another example arises from coding theory where one wishes to find binary codes as large as possible that can correct a prespecified number of errors. The problem can be solved by solving the maximum clique problem in a corresponding graph. Also we discuss generation of random graphs with known maximum clique size. Furthermore, we present algorithms that generate all of the graphs discussed. As the graph generators are the main purpose of this paper they are thoroughly described in the text and the pseudocode of every generator is provided. In the last section we briefly describe two different maximum clique algorithms, and present some computational results revealing some interesting differences between the ``hardness'' of the different test problems and the algorithms. \section{Coding Theory Problems} In this section we will describe how coding theory problems can be interpreted as maximum clique problems on graphs and we will present the graph generators that produce these graphs. In Coding Theory, one wishes to find a binary code as large as possible that can correct a certain number of errors for a given size of the binary words (vectors), see \cite{Bro,Slo}. In order to correct errors, the code must consist of binary words among which any two differ in a certain number of positions so that a misspelled word can be detected and corrected. A misspelled word is corrected by replacing it with the word from the code that differs the least from the misspelled one. The Hamming distance between the binary vectors $u=(u_1,u_2,\ldots,u_n)$ and $v=(v_1,v_2,\ldots,v_n)$ is the number of indices $i$ such that $1\leq i \leq n$ and $u_i\neq v_i$. We denote the Hamming distance by $dist(u,v)$. It is well known that a binary code consisting of a set of binary vectors any two of which have Hamming distance greater or equal to $d$ can correct $\lfloor \frac{d-1}{2} \rfloor$ errors (see \cite{WS}). Thus, what a coding theorist would like to find is the maximum number of binary vectors of size $n$ with Hamming distance $d$. We denote this number by $A(n,d)$. Another problem arising from Coding Theory, closely related to the one mentioned above, is to find a weighted binary code, that is, to find the maximum number of binary vectors of size $n$ that have precisely $w$ 1's and the Hamming distance of any two of these vectors is $d$. This number is denoted by $A(n,w,d)$. A binary code consisting of vectors of size $n$, weight $w$ and distance $d$, can correct $w-\frac{d}{2}$ errors (see \cite{WS}). \subsection{Hamming Graphs} We define the Hamming graph $H(n,d)$, of size $n$ and distance $d$, as the graph with vertex set the binary vectors of size $n$ in which two vertices are adjacent if their Hamming distance is {\em at least} $d$. Then, $A(n,d)$ is the size of a maximum clique in $H(n,d)$. The graph $H(n,d)$ has $2^n$ vertices, $2^{n-1}\sum_{i=d}^{n} {n \choose i}$ edges and the degree of each vertex is $\sum_{i=d}^{n} {n \choose i}$. \subsubsection{Generator of Hamming Graphs} \label{sss:hamm} To generate the Hamming graph corresponding to specified values of $n,\ d$, we would like to represent each binary vector by a decimal integer in such a way that every digit of the binary vector can be recovered easily from the decimal integer. The easiest way to represent a binary word by a decimal integer is by its decimal equivalence. Also, this representation allows for a quick recovery of any digit of the vector, as we see next. Let \begin{eqnarray} (x)_{10} & = & (a_{n-1} \cdots\, a_{i+1}\, a_i\, a_{i-1} \cdots\, a_0)_2 \label{eq:comp1} \\ & = & (a_{n-1}2^{n-1}+ \cdots +a_{i+1}2^{i+1}+a_i2^i+ a_{i-1}2^{i-1}+ \cdots +a_0)_{10} \nonumber \end{eqnarray} such that $x \in {\bf Z}^{+}$ and $a_i \in \{0,1\},\ 0 \leq i \leq n-1$, where $(u)_{b}$ denotes an integer $u$ in base $b$. It is easy to see that \begin{displaymath} a_{i}= \lfloor \frac{x}{2^{i}} \rfloor \bmod 2. \end{displaymath} \begin{figure} {\footnotesize \begin{tabbing} 00000000000000000000\=0\=123\=456\=678\=901\=234\=567\= \kill \>{\bf Program} Hamming Graph \+ \\ \> 1 \> $vsize \leftarrow$ binary vector size \\ \> 2 \> $d \leftarrow$ Hamming distance \\ \> 3 \> $outfile \leftarrow$ output file name \\ \> 4 \> $n \leftarrow 2^{vsize}$ \\ \> 5 \> {\bf write}($outfile$) $n$ \\ \> 6 \> {\bf for} $vert1 = 0$ {\bf to} $n-2$ {\bf do} \\ \> 7 \> \> {\bf for} $vert2 = vert1+1$ {\bf to} $n-1$ {\do} \\ \> 8 \> \> \> $dist \leftarrow 0$ \\ \> 9 \> \> \> {\bf for} $pos = 0$ {\bf to} $n-1$ {\bf do} \\ 10 \> \> \> \> \> {\bf if} ($\lfloor \frac{vert1}{2^{pos}} \rfloor \bmod 2 \neq\ \lfloor \frac{vert2}{2^{pos}} \rfloor \bmod 2$) {\bf then} \\ 11 \> \> \> \> \> \> $dist \leftarrow dist+1$ \\ 12 \> \> \> \> \> {\bf endif} \\ 13 \> \> \> \> {\bf endfor} \\ 14 \> \> \> \> {\bf if} ($dist \geq d$) {\bf then} \\ 15 \> \> \> \> \> {\bf write}($outfile$) {\bf TRUE} \\ 16 \> \> \> \> {\bf else} \\ 17 \> \> \> \> \> {\bf write}($outfile$) {\bf FALSE} \\ 18 \> \> \> \> {\bf endif} \\ 19 \> \> \> {\bf endfor} \\ 20 \> \> {\bf endfor} \\ \end{tabbing} } \caption{Generator of Hamming graphs} \label{alg:hamm} \end{figure} In the computer code that generates Hamming graphs, the user enters the binary vector size, {\em vsize}, the Hamming distance, $d$, and the name of the file in which the user wants to save the graph, {\em outfile} (see the first three lines in figure~\ref{alg:hamm}). The graph generator uses two integer variables, {\em vert\/}1 and {\em vert\/}2, that represent the binary vectors. Since the graph is undirected the adjacency matrix is symmetric, and {\em vert\/}1,\ \ {\em vert\/}2 are assigned every possible value so that $0 \leq vert1 < vert2 \leq |V|-1$. This is done in the two nested loops in lines six and seven in figure~\ref{alg:hamm}. To find whether {\em vert\/}1 and {\em vert\/}2 are adjacent or not, we have to check in how many positions the vectors {\em vert\/}1 and {\em vert\/}2 differ by checking whether the ${\em pos}$-th digit of the two vectors, ${\em pos} = 0,1,\ldots,{\em vsize}-1${\em pos}, is the same or not. This is done by testing whether \begin{displaymath} \lfloor \frac{vert1}{2^{pos}} \rfloor \bmod 2 = \lfloor \frac{vert2}{2^{pos}} \rfloor \bmod 2. \end{displaymath} If true, increment the counter {\em dist}. Once all components are tested, then if $dist \geq d$, {\em vert\/}1 and {\em vert\/}2 are connected in the graph and {\em true} is written to the output file. Else, they are not connected and {\em false} is written to the output file (this is done in lines 14 through 18). The program uses {\em vsize} to calculate the number of vertices in the graph, $|V| = 2^{\em vsize}$, and writes the result to the output file so that the size of the graph is easily found by the program in which the graph will be input. Then, the adjacency matrix of the graph will be saved by writing {\em true} when two vertices are connected and {\em false} when they are not. The entries in the output file correspond to the upper half of the adjacency matrix. The first $|V|-1$ entries in the output file form the first row in the matrix, the next $|V|-2$ entries form the second row, and so on. Hence, the output file will contain an integer denoting the graph size, followed by $\frac{|V|(|V|-1)}{2}$ {\em true} or {\em false}. \subsection{Johnson Graphs} We define the Johnson graph, $J(n,w,d)$, with parameters $n$, $w$ and $d$, as the graph with vertex set the binary vectors of size $n$ and weight $w$, where two vertices are adjacent if their Hamming distance is {\em at least} $d$. Then, similar to Hamming graph, the size of the weighted code, $A(n,w,d)$, equals the size of the maximum clique in $J(n,w,d)$. The graph $J(n,w,d)$ has $n \choose w$ vertices, $\frac{1}{2} {n \choose w} \sum_{k=\lceil \frac{d}{2} \rceil}^{w} {w \choose k} {n-w \choose k}$ edges and the degree of each vertex is $\sum_{k=\lceil \frac{d}{2} \rceil}^{w} {w \choose k} {n-w \choose k}$. \subsubsection{Generator of Johnson Graphs} Again, when constructing the graph, we would like to represent the nodes, labeled by the binary vectors, by decimal integers. In this case, it is not as easy as with the Hamming graph since the vectors that are in the vertex set are not all the binary vectors of size $n$. Thus, we find appropriate to represent each vector by a list of indices in which the positions of the components that equal to 1 are stored. Since we have to examine every pair of vectors in the vertex set to see whether they are adjacent or not in $J(n,w,d)$, the index lists must be such that every binary vector that corresponds to a vertex is represented. We do this by assigning a numerical order to the lists, as follows. Let $u^{(k)}=(u_{n},u_{n-1},\ldots ,u_{1})$ where $1 \leq k \leq {n \choose w}$, be a binary vector in the vertex set of $J(n,w,d)$ represented by the index list $index = (i_{1},i_{2},\cdots ,i_{w})$ where $i_{j},\ 1 \leq j \leq w$, is the index of the $j$-th 1 from the {\em right} of $u^{(k)}$. To update {\em index} into representing $u^{(k+1)}$ instead of $u^{(k)}$, $u^{(k)} < u^{(k+1)},\ 1 \leq k \leq {n \choose w}-1$, find the smallest $j,\ 1 \leq j \leq w$, such that $i_{j+1}-i_{j} \leq 2$ and increment $i_{j}$ by 1. Then, for all $m,\ 1 \leq m < j$, set $i_{m} = m$. In other words, find the first $u_{i_{j}} = 1$ from the right in $u^{(k)}$ which has a 0 to its left and move that 1 one step to the left, then move all the 1s with index less than $i_{j}$ in $u^{(k)}$ as far to the right as possible. We illustrate these ideas with the following example: {\rm Let} \begin{eqnarray*} u^{(k)} & = & (0,1,0,1,1,1,0,0) \\ index & = & (3,4,5,7). \end{eqnarray*} {\rm Using our method, we find that the third 1 from the right is the first to have a 0 to its left. We move that 1 one step to the left and we shuffle the less significant 1's to the right. This results to:} \begin{eqnarray*} u^{(k+1)} & = & (0,1,1,0,0,0,1,1) \\ index & = & (1,2,6,7). \end{eqnarray*} {\rm which is the next binary word in numerical order that has $w$ ones.} \begin{figure} {\scriptsize \begin{tabbing} 00000000000000000000\=0\=123\=456\=678\=901\=234\=567\=l \+ \+ \kill \< {\bf Program} Johnson Graph \\ 1 \> $vsize \leftarrow$ binary vector size \\ 2 \> $w \leftarrow$ vector weight \\ 3 \> $d \leftarrow$ Hamming distance \\ 4 \> $outfile \leftarrow$ output file name \\ 5 \> $n \leftarrow {vsize \choose w}$ \\ 6 \> {\bf write}($outfile$) $n$ \\ 7 \> {\bf for} $one = 1$ {\bf to} $w+1$ {\bf do} \\ 8 \> \> $index1[one] \leftarrow vsize$ \\ 9 \> {\bf endfor} \- \\ 10 \> \> {\bf for} $vert1 = 1$ {\bf to} $n-1$ {\bf do} \\ 11 \> \> \> $moved \leftarrow$ {\bf FALSE} \\ 12 \> \> \> {\bf for} $one = 1$ {\bf to} $w$ {\bf do} \\ 13 \> \> \> \> {\bf if} ($\neg moved$) {\bf then} \\ 14 \> \> \> \> \> {\bf if} ($index1[one] < index1[one+1]-1)$ {\bf then} \\ 15 \> \> \> \> \> \> $index1[one] \leftarrow index1[one]+1$ \\ 16 \> \> \> \> \> \> $moved \leftarrow$ {\bf TRUE} \\ 17 \> \> \> \> \> {\bf else} \\ 18 \> \> \> \> \> \> $index1[one] \leftarrow one$ \\ 19 \> \> \> \> \> {\bf endif} \\ 20 \> \> \> \> {\bf endif} \\ 21 \> \> \> \> $index2[one] \leftarrow index1[one]$ \\ 22 \> \> \> {\bf endfor} \\ 23 \> \> \> {\bf for} $vert2 = vert1+1$ {\bf to} $n$ {\bf do} \\ 24 \> \> \> \> $dist \leftarrow 0$ \\ 25 \> \> \> \> $moved \leftarrow$ {\bf FALSE} \\ 26 \> \> \> \> {\bf for} $one = 1$ {\bf to} $w$ {\bf do} \\ 27 \> \> \> \> \> {\bf if} ($\neg moved$) {\bf then} \\ 28 \> \> \> \> \> \> {\bf if} ($index2[one] < index2[one+1]-1$) {\bf then} \\ 29 \> \> \> \> \> \> \> $index2[one] \leftarrow index2[one]+1$ \\ 30 \> \> \> \> \> \> \> $moved \leftarrow$ {\bf TRUE} \\ 31 \> \> \> \> \> \> {\bf else} \\ 32 \> \> \> \> \> \> \> $index2[one] \leftarrow one$ \\ 33 \> \> \> \> \> \> {\bf endif} \\ 34 \> \> \> \> \> {\bf endif} \\ 35 \> \> \> \> \> $equal \leftarrow$ {\bf FALSE} \\ 36 \> \> \> \> \> {\bf for} $m = 1$ {\bf to} $w$ {\bf do} \\ 37 \> \> \> \> \> \> {\bf if} ($index2[one] = index1[m]$) {\bf then} \\ 38 \> \> \> \> \> \> \> $equal \leftarrow$ {\bf TRUE} \\ 39 \> \> \> \> \> \> {\bf endif} \\ 40 \> \> \> \> \> {\bf endfor} \\ 41 \> \> \> \> \> {\bf if} ($\neg equal$) {\bf then} \\ 42 \> \> \> \> \> \> $dist\leftarrow dist+2$ \\ 43 \> \> \> \> \> {\bf endif} \\ 44 \> \> \> \> {\bf endfor} \\ 45 \> \> \> \> {\bf if} ($dist \geq d$) {\bf then} \\ 46 \> \> \> \> \> {\bf write}($outfile$) {\bf TRUE} \\ 47 \> \> \> \> {\bf else} \\ 48 \> \> \> \> \> {\bf write}($outfile$) {\bf FALSE} \\ 49 \> \> \> \> {\bf endif} \\ 50 \> \> \> {\bf endfor} \\ 51 \> \> {\bf endfor} \\ \end{tabbing} } \caption{Generator of Johnson graphs} \label{alg:john} \end{figure} The Johnson graph generator is given in figure~\ref{alg:john}. In the generator, the vector size, {\em vsize=n} and weight $w$, as well as the Hamming distance, $d$, and output file, {\em outfile}, are given as input. The graph size, ${vsize \choose w}$, is calculated and written to the output file so that the size of the graph can easily be determined by any other program, using the adjacency matrix of a graph as input. Again, during execution, we will write {\em true} and {\rm false} to the output file, in the same manner as for Hamming graphs. Next, one of the two index lists, {\em index\/}1, is initialized by setting the $w+1$ first positions to $vsize$ (see lines 7--9). Note that here we use an index list of length $w+1$ and not of length $w$ as we did when describing the idea in the previous section. This is only because when the list is updated for the first time, after the initialization, the updating algorithm will find that no 1 in the corresponding binary vector has a 0 to its left and therefore will shift all the 1's to the right, just where we want them in our starting list. Note also that {\em index}2 does not have to be initialized since {\em index}1 is copied to {\em index}2 after the updating (see line 21 in figure~\ref{alg:john}). With {\em index\/}1 initialized, we can start examining every pair of vectors to see if they are adjacent or not. Just like for the Hamming graph, this is done in two nested for-loops where the decimal integers {\em vert\/}1 and {\em vert\/}2, representing the vertices, are assigned every possible value such that $1 \leq vert1 < vert2 \leq n$. The first thing that is done in each loop is the updating of the index lists. {\em Index\/}1, representing the vector corresponding to {\em vert\/}1, is updated in the outer loop while {\em index\/}2 is updated in the inner loop. They are both updated in the same way so we only describe the procedure of updating {\em index\/}1. To do this, we use a flag called {\em moved} which is initially set to {\em false}. Then we look through the index list, using yet another for-loop, and examine every index $i_{one},\ one = 1,2,\ldots,w$ to see whether the corresponding 1 has a 0 to its left or not. If it has not, we put the 1 back to its starting position by setting $index1[one] = one$. Otherwise, if the {\em one}-th 1 has a 0 to its left we increase $index1[one]$ by one and set {\em moved} to {\em true} because now the list is updated and we do not want anything more to be done while finishing the loop. We then assign the same values to {\em index\/}2. Thus, when {\em index\/}2 is updated in the beginning of the inner loop, it is given the values corresponding to the vector following in numerical order the one represented by {\em index\/}1. In figure~\ref{alg:john}, {\em index\/}1 is updated in lines 11 through 22 and {\em index\/}2 in lines 25 through 34. When both lists are updated we can check the adjacency condition. This is done within the updating loop of {\em index\/}2 in the following way: for every index {\em one} we check if $index2[one] = index1[m],\ m = 1,2,\ldots ,w$ (lines 36--40 in the figure). If so, we increase the counter {\em dist} by 2. It is increased by 2 because if there is a 1 in one of the vectors in a position where the other vector has a 0, then the latter has to have a position which has a 1 while the former has a 0. Hence, the Hamming distance is increased by 2 for every unequal value in the index lists (lines 41--43 in the figure). Finally, we check whether $dist \geq d$, and if so, write {\em true} to the output file, otherwise {\em false} (lines 45--49). \section{Problems Arising From Keller's Conjecture} A family of hypercubes with disjoint interiors whose union is the Euclidean space ${\bf R}^{n}$ is a {\em tiling}. A lattice tiling is a tiling for which the centers of the cubes form a lattice. In the beginning of the century, Minkowski conjectured that in a lattice tiling of ${\bf R}^{n}$ by translates of a unit hypercube, there exist two cubes that share a $(n-1)$-dimensional face. About fifty years later, Haj\"{o}s \cite{Haj} proved Minkowski's conjecture. At 1930, Keller suggested that Minkowski's conjecture holds even in the absence of the lattice assumption. Ten years later Perron \cite{Per} proved the correctness of Keller's conjecture for $n \leq 6$. Since then, many papers have been devoted to prove or disprove this conjecture and recently, Lagarias and Shor \cite{Lag} proved that Keller's conjecture fails for $n \geq 10$. Thus, it is left to prove whether the conjecture holds for $n = 7,8,9$. \subsection{The Keller Graphs $\Gamma_{n}$} We define the graph $\Gamma_{n}$ as a graph with vertex set $V_{n} = \{(d_{1},d_{2},\ldots,d_{n}) : d_{i} \in \{0,1,2,3\},\ i=1,2,\ldots,n\}$ where two vertices $u = (d_{1},d_{2},\ldots,d_{n})$ and $v = (d'_{1},d'_{2},\ldots,d'_{n})$ in $V_{n}$ are adjacent if and only if \begin{equation} \exists\, i,\ 1 \leq i \leq n : d_{i}-d'_{i} \equiv {2 \bmod 4} \label{eq:kgrt} \end{equation} and \begin{equation} \exists\, j \neq i,\ 1 \leq j \leq n : d_{j} \neq d'_{j}. \label{eq:diff} \end{equation} In \cite{Cor}, Corr\'{a}di and Szab\'{o} presented a graph theoretic equivalent of Keller's conjecture. It is shown that, there is a counterexample to Keller's conjecture if and only if there exist a $n \in {\bf N^{+}}$ such that $\Gamma_{n}$ has a clique of size $2^{n}$. $\Gamma_{n}$ has $4^{n}$ vertices, $\frac{1}{2} 4^{n}(4^{n}-3^{n}-n)$ edges and the degree of each node is $4^{n}-3^{n}-n$. $\Gamma_{n}$ is very dense and has at least $8^{n}n!$ different maximum cliques. It can be shown (see \cite{Lag}) that the maximum clique size of $\Gamma_{n}$ is less than or equal to $2^{n}$. \subsubsection{The $\Gamma_{n}$ Generator} \begin{figure} {\footnotesize \begin{tabbing} 00000000000000000000\=0\=123\=456\=678\=901\=234\=567\=l \+ \+ \kill \< {\bf Program} Keller Graph \\ 1 \> $vsize \leftarrow$ binary vector size \\ 2 \> $outfile \leftarrow$ output file name \\ 3 \> $n \leftarrow 4^{n}$ \\ 4 \> {\bf write}($outfile$) $n$ \\ 5 \> {\bf for} $vert1 = 0$ {\bf to} $n-2$ {\bf do} \\ 6 \> \> {\bf for} $vert2 = vert1+1$ {\bf to} $n-1$ {\bf do} \\ 7 \> \> \> $kongrt \leftarrow$ {\bf FALSE} \\ 8 \> \> \> $diff \leftarrow$ {\bf FALSE} \\ 9 \> \> \> {\bf for} $pos = 1$ {\bf to} $vsize-1$ {\bf do} \- \\ 10 \> \> \> \> \> $comp1 \leftarrow {\frac{vert1}{4^{pos}} \bmod 4}$ \\ 11 \> \> \> \> \> $comp2 \leftarrow {\frac{vert2}{4^{pos}} \bmod 4}$ \\ 12 \> \> \> \> \> $sub \leftarrow \left| comp1-comp2 \right|$ \\ 13 \> \> \> \> \> {\bf if} ($sub = 2 \wedge \neg kongrt$) {\bf then} \\ 14 \> \> \> \> \> \> $kongrt \leftarrow$ {\bf TRUE} \\ 15 \> \> \> \> \> {\bf elseif} ($sub \neq 0$) {\bf then} \\ 16 \> \> \> \> \> \> $diff \leftarrow {\bf TRUE}$ \\ 17 \> \> \> \> \> {\bf endif} \\ 18 \> \> \> \> {\bf endfor} \\ 19 \> \> \> \> {\bf if} ($kongrt \wedge diff$) {\bf then} \\ 20 \> \> \> \> \> {\bf write}($outfile$) {\bf TRUE} \\ 21 \> \> \> \> {\bf else} \\ 22 \> \> \> \> \> {\bf write}($outfile$) {\bf FALSE} \\ 23 \> \> \> \> {\bf endif} \\ 24 \> \> \> {\bf endfor} \\ 25 \> \> {\bf endfor} \\ \end{tabbing} } \caption{Generator of Keller graphs} \label{alg:kell} \end{figure} To construct the graph $\Gamma_n$, we use the same method for calculating the vector components as we did with the Hamming graph in section~\ref{sss:hamm} with the exception of interpreting the vertices as integers in base 4 instead of in base 2. Thus, if we have a vector $u = (u_{n-1},u_{n-2},\ldots,u_{0})$ such that $u_{i} \in \{0,1,2,3\},\ 0 \leq i \leq n-1$, and if we represent $u$ by its corresponding decimal integer \begin{displaymath} x = u_{n-1}4^{n-1}+u_{n-2}4^{n-2}+ \cdots +u_{i}4^{i}+ \cdots +u_{0} \end{displaymath} then we can calculate any coefficient $u_{i}$ as we did for the Hamming graph by \begin{displaymath} u_{i} = {\lfloor \frac{x}{4^{i}} \rfloor \bmod 4},\ 0 \leq i \leq n-1. \end{displaymath} An algorithm to generate $\Gamma_{n}$ is given in figure~\ref{alg:kell}. As usual, the vector size, {\em vsize}, and the output file, {\em outfile}, is given as input by the user. Then, the graph size $n = 4^{\em vsize}$ is calculated and written to the output file (see lines 1--4 in the figure). In the two for-loops (starting at lines 5 and 6) we let {\em vert\/}1 and {\em vert\/}2 represent all pairs of nodes. By using two flags, {\em kongrt} and {\em diff}, we test the connectivity conditions (\ref{eq:kgrt}) and (\ref{eq:diff}) for each such pair of nodes. This is done by initializing {\em kongrt} and {\em diff} to {\em false}. Then, for every position {\em pos} in the vectors, we calculate the difference {\em sub}, between the {\em pos\/}-th component {\em comp\/}1 of node {\em vert\/}1 and the {\em pos\/}-th component {\em comp\/}2 of node {\em vert\/}2 (lines 10--12). Furthermore, if {\em sub} equals 2, i.e. if \begin{displaymath} comp1-comp2 \equiv {2 \bmod 4}, \end{displaymath} and {\em kongrt = false}, then {\em pos} is the first position in the vectors such that the congruence condition (\ref{eq:kgrt}) is fulfilled and we set {\em kongrt} to {\em true} (lines 13--14). Then, if {\em diff} is still {\em false}, we test only the difference condition (\ref{eq:diff}) and if found true, then set {\em diff} to {\em true} (lines 15--16). When both {\em diff} and {\em kongrt} are {\em true}, {\em vert\/}1 and {\em vert\/}2 are adjacent in $\Gamma_{n}$ and we write {\em true} to the output file, otherwise, as usual, {\em false} (lines 19--23). Again, the output file consists of the graph size followed by the upper half of the adjacency matrix. \section{Problems Arising From Fault Diagnosis} A crucial problem in studying the reliability of large multiprocessor systems, is the problem known as system-level fault diagnosis. The task is to identify all faulty processors (units) in the system. The classical approach to fault diagnosis was originated over twenty years ago by Preparata, Metze and Chien \cite{PMC}, leading to a fault diagnosis model known as the PMC model. In the PMC model each unit can test some other units and it is assumed that fault-free units always give the correct results while faulty ones are unpredictable and can output any results. Furthermore, it is assumed that the number of faulty units never exceed some upper bound $t$. Upon completion of all tests, the results are gathered by a monitoring unit which computes the status of all units based on the gathered results. The assumption that a fault-free unit always detects faulty units may seem a little optimistic. Also, the upper bound assumption may restrict the model to unrealistic situations. Further,the PMC model is accurate only if the upper bound $t$ does not exceed the number of neighbors of any unit. For large systems however, the connectivity might be fairly low, making it quite probable that the number of faulty units exceed the number of neighbors for some units. Yet another assumption in the PMC model, the existence of a central monitoring unit, makes it less reliable. In order to overcome this problem, distributed fault-tolerance was introduced. The goal of this approach is to find a way to let every fault-free unit to be able to determine the status of every other unit. The above observations have led to several different models one of which was introduced by Blough \cite{Blo}. In his model, processors test each other and fault-free units always detect other fault-free processors correctly, while they detect faulty processors with a fixed probability less than 1. No assumption is made about how faulty units behave as testers. \subsection{C-Fat Rings} In \cite{Ber}, Berman and Pelc study a realistic approach to fault diagnosis by simultaneously relaxing all the three assumptions from the PMC model described above. Their model is based on a probabilistic model presented by Blough performed in a distributed fashion. Consequently, a processor can never be sure that the information it receives is correct. Berman and Pelc define a system design represented by a class of graphs, $G_{n}$. They show that the probability of correct diagnosis of fault processors for such systems, happens with probability at least $1-n^{-1}$. The algorithm they propose is based on a model where a test by a fault-free unit on a faulty one does not detect a fault with probability $q$, while they assume that fault-free units never detect faults in each other. For a given parameter $c$, a c-fat ring is the graph $G=(V,E)$ defined as follows. Let \begin{displaymath} k = \lfloor \frac{|V|}{c\log |V|} \rfloor \end{displaymath} and let $W_{0},\ldots,W_{k-1}$ be a partition of $V$ such that \begin{equation} \label{eq:card} c\log |V| \leq |W_{i}| \leq 1+ \lceil c\log |V| \rceil\ {\rm for}\ i= 0,1,\ldots,k-1. \end{equation} For $u \in W_{i}$ and $v \in W_{j}$ we have $(u,v) \in E$ iff $u \neq v$ and $|i-j| \in \{0,1,k-1\}$. \begin{figure} {\footnotesize \begin{tabbing} 00000000000000000000\=0\=123\=456\=678\=901\=234\=567\= \+ \+ \kill \< {\bf Program} C-fat ring \\ 1 \> $c \leftarrow$ c\\ 2 \> $n \leftarrow$ number of vertices \\ 3 \> $outfile \leftarrow$ output file name \\ 4 \> {\bf write}($outfile$) $n$ \\ 5 \> $k \leftarrow \lfloor \frac{n}{c \log n} \rfloor$ \\ 6 \> {\bf for} $vert1 = 0$ {\bf to} $n-2$ {\bf do} \\ 7 \> \> $part1 \leftarrow {vert1 \bmod k}$ \\ 8 \> \> {\bf for} $vert2 = vert1+1$ {\bf to} $n-1$ {\bf do} \\ 9 \> \> \> $part2 \leftarrow {vert2 \bmod k}$ \- \\ 10 \> \> \> \> {\bf if} ($\left| part1-part2 \right| \leq 1 \vee \left| part1-part2 \right|= k-1$) {\bf then} \\ 11 \> \> \> \> \> {\bf write}($outfile$) {\bf TRUE} \\ 12 \> \> \> \> {\bf else} \\ 13 \> \> \> \> \> {\bf write}($outfile$) {\bf FALSE} \\ 14 \> \> \> \> {\bf endif} \\ 15 \> \> \> {\bf endfor} \\ 16 \> \> {\bf endfor} \\ \end{tabbing} } \caption{The c-fat ring generator} \label{alg:cfat} \end{figure} A major step in the algorithm proposed in \cite{Ber} is to find the maximum clique of a c-fat ring. Therefore we construct a c-fat ring generator and perform some computations to see how the maximum clique algorithms perform on such graphs. \subsubsection{C-Fat Ring Generator} \label{sss:cfat} An algorithm that generates c-fat rings is given in figure~\ref{alg:cfat}. It works in a manner similar to the other algorithms given earlier in this paper. At first the input $|V|$ and $c$ is given, that is, the graph size and the partition parameter. Then the number of partitions $k = \lfloor \frac{n}{c\log n} \rfloor$ is calculated (see line 5 in figure~\ref{alg:cfat}). The two for-loops assign values to {\em vert\/}1 and {\em vert\/}2 so that every two nodes are tested to see whether they are connected or not. Two nodes are connected if they are members of the same or adjacent partitions. We represent the nodes of $G$ by the integers $0,1,\ldots,n-1$. For convenience we let the $i$-th, $0 \leq i \leq k-1$, part of the partition to contain the vertices labeled $i\cdot m,\ m = 1,2,\ldots,|W_{i}|$, where $|W_{i}|$, the cardinality of partition $i$ which is given in equation~\ref{eq:card}. By construction, every other $k$-th node is found in the same partition. This gives us an easy way to calculate which partition a node belongs to. Namely, the partition {\em comp\/}1 to which {\em vert\/}1 belongs to is calculated by \begin{displaymath} comp1 = vert1 \bmod k \end{displaymath} (see lines 7 and 9 in the figure). When {\em comp\/}1 and {\em comp\/}2 are calculated we test whether the difference $|comp\/1 - comp\/2|$ is in $\{0,1,k-1\}$. In this case, {\em true} is written to the output file, otherwise {\em false} (see lines 10--13). As in the previous sections, the output produced corresponds to the upper half of the adjacency matrix. \section{Graphs With Specified Clique Size and Density} In \cite{San1,San2} Sanchis proposes an algorithm for generating instances of the vertex covering problem. Regarding the difficulty of the problems generated, the reader is referred to \cite{San1}. The vertex covering is to find the smallest set of vertices $V^{*}$ of a graph $G=(V,E)$ such that every edge in $G$ is incident on at least one vertex in $V^{*}$. This problem is equivalent to solving the maximum clique problem for $\overline{G}$. In this section we generate instances of the vertex covering problem according to Sanchis' algorithm and then convert them into instances of the maximum clique problem by using the complement graphs. Thus, if $G=(V,E)$ is a graph with minimum vertex cover of size $c$ generated by Sanchis' algorithm, then the complement graph $\overline{G}=(V,\overline{E})$ has maximum clique size $cl(\overline{G}) = |V|-c$ (see also \cite{Par}). To produce a graph $G=(V,E)$ with $|V| = n,\ |E| = m$ with minimum vertex cover of size $c$, Sanchis proposes the following. Let $k = n-c$. Choose a partition of the integer $n$ into $k$ parts $n_{1},\ldots,n_{k}$, where $n_{1}+n_{2}+\cdots+n_{k} = n$ such that $m' = \sum_{i=1}^{k} {n_{i} \choose 2} \leq m$. Form $k$ cliques with sizes $n_{1},n_{2},\ldots,n_{k}$. For each $i,\ 1 \leq i \leq k$, choose $n_{i}-1$ vertices from the $i$-th clique to be in the vertex cover. Add $m-m'$ additional edges to the graph in such way that each added edge is incident on at least one of the selected cover vertices. We can see the graph $G = (V,E)$ with $|V| = n,\ |E| = m$ and a minimum vertex cover of size $c$ does not exist unless \begin{equation} 0 \leq c \leq n-1 \label{eq:ccond} \end{equation} and \begin{equation} r{{b+1} \choose 2}+(k-r){b \choose 2} \leq m \leq {c \choose 2} +kc \label{eq:mcond} \end{equation} where $k = n-c$ and $n = kb+r$. This follows from the fact that a graph with $n$ vertices and minimum vertex cover of size $c$ can have at most ${c \choose 2}$ edges connecting cover vertices plus $c(n-c) = ck$ edges connecting cover to noncover vertices. Furthermore, a graph with $n$ vertices and minimum vertex cover of size $c$ must have at least $r{{b+1} \choose 2}+(k-r){b \choose 2}$ vertices (see \cite{San2}). Therefore, the algorithm works only on input $n,\ m,\ c$ that fulfills the conditions (\ref{eq:ccond}) and (\ref{eq:mcond}) above. \subsubsection{Generator for Graphs with known Clique} \begin{figure} {\footnotesize \begin{tabbing} 00000000000000000000\=0\=123\=456\=678\=901\=234\=567\= \+ \+ \kill \< {\bf Program} Sanchis graph \\ 1 \> $n \leftarrow$ number of vertices\\ 2 \> $m \leftarrow$ number of edges \\ 3 \> $c \leftarrow$ cover size \\ 4 \> $seed \leftarrow$ random number generator seed \\ 5 \> $outfile \leftarrow$ output file name \\ 6 \> $k \leftarrow n-c$ \\ 7 \> $i \leftarrow 6$ \\ 8 \> $edges \leftarrow 0$ \\ 9 \> {\bf write}($outfile$, rec=$i$) $n$ \- \\ 10 \> \> {\bf for} $vert1 = 0$ {\bf to} $n-2$ {\bf do} \\ 11 \> \> \> {\em part\/}1 $\leftarrow {vert1 \bmod k}$ \\ 12 \> \> \> {\bf for} $vert2 = vert1+1$ {\bf to} $n-1$ {\bf do} \\ 13 \> \> \> \> {\em part\/}2 $\leftarrow {vert2 \bmod k}$ \\ 14 \> \> \> \> $i \leftarrow i+1$ \\ 15 \> \> \> \> {\bf if} ($part1 = part2$) {\bf then} \\ 16 \> \> \> \> \> {\bf write}($outfile$, rec=$i$) {\bf TRUE} \\ 17 \> \> \> \> \> $edges \leftarrow edges+1$ \\ 18 \> \> \> \> {\bf else} \\ 19 \> \> \> \> \> {\bf write}($outfile$, rec=$i$) {\bf FALSE} \\ 20 \> \> \> \> {\bf endif} \\ 21 \> \> \> {\bf endfor} \\ 22 \> \> {\bf endfor} \\ 23 \> \> {\bf while} ($edges < m$) {\bf do} \\ 24 \> \> \> $vert1 \leftarrow vert2$ \\ 25 \> \> \> {\bf while} (vert1 = vert2) {\bf do} \\ 26 \> \> \> \> $vert1 \leftarrow 1+k+(n-k)\cdot{\bf random}(seed)$ \\ 27 \> \> \> \> $vert2 \leftarrow 1+n\cdot{\bf random}(seed)$ \\ 28 \> \> \> {\bf endwhile} \\ 29 \> \> \> {\bf if} ($vert1 < vert2$) {\bf then} \\ 30 \> \> \> \> $vert1 \leftrightarrow vert2$ \\ 31 \> \> \> {\bf endif} \\ 32 \> \> \> $pairs \leftarrow \frac{n(n-1)}{2}$ \\ 33 \> \> \> $rowrest \leftarrow \frac{(n-vert1)(n-vert1-1)}{2}$\\ 34 \> \> \> $colrest \leftarrow n-vert2$ \\ 35 \> \> \> $i \leftarrow 6+pairs-rowrest-colrest$ \\ 36 \> \> \> {\bf read}($outfile$, rec=$i$) tmp \\ 37 \> \> \> {\bf if} ($\neg tmp$) {\bf then} \\ 38 \> \> \> \> {\bf write}($outfile$, rec=$i$) {\bf TRUE} \\ 39 \> \> \> \> $edges \leftarrow edges+1$ \\ 40 \> \> \> {\bf endif} \\ 41 \> \> {\bf endwhile} \\ \end{tabbing} } \caption{Generator for graphs with known Clique} \label{alg:sanc} \end{figure} In the algorithm presented here, $n$ is partitioned in $k$ parts of nearly equal size and the additional edges are chosen randomly. The generator is given in figure~\ref{alg:sanc}. As usual the input is given by the user, and it must fulfill conditions (\ref{eq:ccond}) and (\ref{eq:mcond}). A seed to the {\bf random}-procedure is also given. In this algorithm we write to the output file in a somewhat different way than before. To each {\em true, false} value that we write to the output file, we associate a pointer $i$. Effectively, we treat the values {\em true\/}, {\em false\/} as records. This way, the algorithm will be able to update the value of a record from {\em false\/} to {\em true} when the corresponding edge is added. The graph size $n$ is, as seen in lines 6 and 9 in the figure, written in 6 positions to the output file, so the graph can not have more than 999999 vertices, unless the source code is modified. To proceed on the algorithm, we represent every pair of nodes {\em vert\/}1, {\em vert\/}2 ($0 \leq vert1 < vert2 \leq n-1$) in two for-loops, and we include {\em vert1\/}1 in the {\em part\/}1 part of the partition, where {\em part\/}1$= {vert1 \bmod k}$ (lines 11 and 13), just as we did with the c-fat rings in section~\ref{sss:cfat}. Within the two for-loops, we connect every pair of nodes that are in the same partition by writing {\em true\/} to the output file if $part1 = part2$, otherwise {\em false}. For every {\em true\/} that we write to the output file we increment the counter {\em edges\/} by one (lines 15--20). Now we have created a graph with $k$ cliques each having size $\lfloor \frac{n}{k} \rfloor$ or $\lfloor \frac{n}{k} \rfloor+1$ and a cover of size $c$ consisting of the nodes labeled $k,k+1,\ldots,n-1$ where the total number of edges equals {\em edges}. Thus, if {\em edges\/} is less than $m$ we have to connect $m-edges$ additional edges to get a graph with the desired number of edges. We do this in a while-loop in which we randomly assign {\em vert\/}1 to a cover vertex and {\em vert\/}2 to any vertex (lines 25--28). The assignment is done in while-loop that ensures that $vert1 \neq vert2$. We make use of a real-valued procedure {\bf random} that takes as argument a {\em seed} and returns a random number $y \in [0,1]$. Suppose we have two nodes, {\em vert\/}1 and {\em vert\/}2, that we would like to connect. To do this we must know the position in the output file corresponding to edge, ({\em vert\/}1,{\em vert\/}2). Also, we need to know whether the value of this entry is already {\em true}. If {\em vert\/}1 is less than {\em vert\/}2 (lines 29--31) we can calculate the corresponding position in the file in the following way. There are 6 positions in which $n$ is written, followed by a total of $pairs = \frac{n(n-1)}{2}$ entries representing edges, which results to a total of $i = 6+pairs$ entries in the file. The $rowrest = \frac{(n-vert1)(n-vert1-1)}{2}$ last entries correspond to edges $(u,v)$ such that $vert1 < u \leq v \leq n-1$. The $colrest = n-vert2$ entries preceding the last $rowrest$ entries correspond to edges $(vert1,v)$ such that $vert2 < v$. Therefore, $i = 6+pairs-rowrest-colrest$ is the position in the file representing the edge $(vert1,vert2)$ (see lines 32--35 in the figure). If this entry is {\em false\/} we change it to {\em true\/} and increment {\em edges\/} by one, otherwise we start again from line 23. \section{Computations} In this section we present some computational experiments using the generated graphs, with two exact algorithms. These computations will help us evaluate the difficulty of the generated instances and the efficiency of the two algorithms. The two algorithms tested are the CP-algorithm presented in \cite{CP}, and the PR-algorithm presented in \cite{PR}. In \cite{PR} the authors present computational results for graphs of up to 1000 vertices and 150000 edges while in \cite{CP} the authors present results for graphs of up to 3000 vertices and over one million edges. Those computations were made on an IBM 3090 computer while our computations were performed on a Sun4 computer. On this machine we were able to solve problems, in a reasonable period of time, where the size of the graphs did not exceed 256 vertices. \subsection{The CP-algorithm} The CP-algorithm presented in \cite{CP} is a simple and efficient algorithm that uses partial enumeration to find the maximum clique in an arbitrary graph. Computations on randomly generated graphs show that it compares favorably with all existing exact algorithms for the maximum clique problem. Next, we give a brief description of the CP-algorithm. Consider the graph $G = (V,E)$. If the graph is dense, the algorithm orders and relabels the vertices so that $v_{1}\in V$ is the vertex of smallest degree in $G$, $v_{2}\in V$ is the vertex of smallest degree in $G-\{v_{1}\}$ and generally, $v_{k}\in V$ is the vertex of smallest degree in $G-\{v_{1},\ldots,v_{k-1}\}$, $1 \leq k \leq n-2$, where $n = |V|$. Empirical tests show that computation time is greatly reduced if the vertex set is ordered in the above way. When the nodes are ordered the algorithm searches through the branch and bound tree in a depth-first manner. The algorithm starts assigning to the root of the tree (at level 1), the vertex $v_1$. Then, $v_1$ is expanded by the vertices $v_2,v_3,\dots,v_n$. Suppose we are at level $d$ of the tree. Then there are $d-1$ vertices in the current partial clique. Assume $v$ is the vertex assigned at level $d-1$. Then, we expand $v$. Suppose $V_{d} = \{v_{d_1},\ldots,v_{d_i},\ldots,v_{d_m}\}$ is the set of all vertices considered at depth $d$ and that the vertices $\{v_{d_1},\ldots,v_{d_{i-1}}\}$ have already been considered. Then $v$ is expanded by $v_{d_i}$. Then, we procced to level $d+1$ by expanding $v_{d_i}$ by all vertices that are adjacent to $v_{d_i}$ and are not included in the current partial clique. The algorithms continues in this fashion. To eliminate branching, the algorithm uses the following branching rule: Let $v_{d_i}$ be the vertex corresponding to level $d$. Then, vertices $\{v_{d_1},\ldots,v_{d_{i-1}}\}$ have already been considered thus allowing for inclusion to the current clique, only vertices in $\{v_{d_{i+1}},\ldots,v_{d_{m}}\}$. This means that the current clique cannot have size bigger than $d+(m-i)$. If this size is less than or equal to the current incumbent size, then it is clear that expansion of $v_{d_i}$ cannot result in a larger clique. In this case the algorithm backtracks to the previous level. If the algorithm is at depth 1 and the inequality holds it terminates and the current clique is maximum. For more details and for the Fortran code see \cite{CP}. %We illustrate the algorithm with a small example. %\begin{example} %\rm %Consider the graph in figure~\ref{fig:cpex} with the steps of the %algorithm shown in table~\ref{tb:cpex}. The CP-algorithm finds $\{3,2,4,7\}$ %to be a maximum clique for this graph. %\end{example} %\input{cpex} \subsection{The PR-algorithm} The PR-algorithm presented in \cite{PR} is a branch and bound algorithm that is based on a quadratic zero-one formulation of the maximum clique problem. This algorithm is proved to be efficient for dense graphs. Solving the maximum clique problem for a graph $G = (V,E)$ with $n = |V|$ vertices, is equivalent to solving the following quadratic zero-one program: \begin{displaymath} \min f({\bf x}) = - \sum_{i = 1}^{n} x_{i} + 2 \sum_{\stackrel{(v_{i},v_{j})\not\in E}{i>j}}x_{i}x_{j},\ \ {\bf x}\in \{0,1\}^{n} \end{displaymath} or equivalently in symmetric form \begin{displaymath} \min f({\bf x}) = {\bf x}^{\rm T}A{\bf x},\ \ A = A_{\overline{G}}-I,\ {\bf x}\in \{0,1\}^{n} \end{displaymath} where $A_{\overline{G}}$ is the adjacency matrix of $\overline{G}$, and $I$ is the $n\times n$ identity matrix. A solution ${\bf x}^{*}$ to the the above program defines a maximum clique $C$ for $G$ as follows: if $x_{i}^{*} = 1$ then $v_{i}\in C$ and if $x_{i}^{*} = 0$ then $v_{i}\not\in C$ with $|C| = -z = -f({\bf x}^{*})$. To solve the problem stated above the algorithm uses a depth-first branch and bound technique by selecting a binary variable, $x_{i}$, and fixing it to zero for one subproblem and to one for the other. To reduce the size of the search tree, the algorithm two different pruning rules. An upper bound rule and a forcing rule. The upper bound rule prunes if a calculated upper bound for the subproblem is less than the current incumbent objective value. The forcing rule prunes by generating only one branch for a given variable if it can be shown that the alternate value can only yield suboptimal solutions. The algorithm can use two different ways of determining the order with which vertices are considered for branching. The greedy approach and the non-greedy approach. The non-greedy approach branches on the vertex of smallest degree first, leading to a small search tree which takes less time to search through and hence, confirmation of optimality takes less time than the greedy approach. On the other hand, the greedy approach branches on the vertex of largest degree first, leading to a large search tree where the maximum clique will be found early in the depth-first search. Of course confirming optimality can not be done until the whole tree is searched which means than the greedy approach is expected to take more time. For these reasons, the greedy approach is only used to heuristically approximate the size of the maximum clique while the actual branching is done by using the non-greedy approach (for details see \cite{PR}). \subsection{Computational Results} The computations were performed on a Sun4 computer with the two exact maximum clique algorithms implemented in Fortran~77. The test graphs where generated by the algorithms described in the previous sections. The sizes of the solved problems vary from 50 to 256 vertices. Our experience as well as the tables presented here indicate that the CP-algorithm is more effective for large problems while the PR-algorithm is faster for dense graphs. However, for graphs with size exceeding 256 vertices, no algorithm managed to produce answers in reasonable amount of time (a few hours). Also we observed that graphs with large maximum clique size are computationally harder. In table~\ref{tb:cfat} we present computational results when the two algorithms are tested on c-fat rings of different characteristics. In the leftmost column, the partition parameter $c$ is given. Note that even though the problems are of moderate size, the CP-algorithm has some difficulties with dense graphs. \begin{table}[tbh] \centering \scriptsize \begin{tabular}{||r|r|r|r|r|r|r||} \hline \multicolumn{7}{|c|}{Computational results for c-fat rings} \\ \hline \hline & \multicolumn{1}{c|}{number of} & \multicolumn{1}{c|}{number of} & \multicolumn{1}{c|}{graph} & \multicolumn{1}{c|}{size of} & \multicolumn{2}{c|}{Avg CPU-time {\tiny (sec)}} \\ \cline{6-7} \multicolumn{1}{||c|}{c} & \multicolumn{1}{|c|}{vertices} & \multicolumn{1}{|c|}{edges} & \multicolumn{1}{|c|}{density} & \multicolumn{1}{|c|}{max clique} & \multicolumn{1}{|c|}{CP-alg} & \multicolumn{1}{|c||}{PR-alg} \\ \hline 1 & 100 & 669 & 14 & 10 & 0.056 & 0.030\\ 2 & 100 & 1450 & 29 & 20 & 0.092 & 0.092 \\ 3 & 100 & 2094 & 42 & 30 & 0.420 & 0.106 \\ 4 & 100 & 2950 & 60 & 40 & 8.102 & 3.096 \\ 5 & 100 & 3700 & 75 & 50 & 104.438 & 3.166 \\ \hline \end{tabular} \caption{Computational results on c-fat rings} \label{tb:cfat} \end{table} In table~\ref{tb:hamm} we present the results from computations on Hamming graphs. In the first column the size $n$ of the binary vector is given and in the second the Hamming distance is given. Again we note that the PR-algorithm is more efficient on dense graphs of moderate size while the CP-algorithm can solve larger problems. \begin{table}[bth] \centering \scriptsize \begin{minipage}{11.1cm} \begin{tabular}{||r|r|r|r|r|r|r|r||} \hline \multicolumn{8}{|c|}{Computational results for Hamming graphs} \\ \hline \hline & & \multicolumn{1}{c|}{number of} & \multicolumn{1}{c|}{number of} & \multicolumn{1}{c|}{graph} & \multicolumn{1}{c|}{size of} & \multicolumn{2}{c|}{Avg CPU-time {\tiny (sec)}} \\ \cline{7-8} \multicolumn{1}{||c|}{n} & \multicolumn{1}{|c|}{dist} & \multicolumn{1}{|c|}{vertices} & \multicolumn{1}{|c|}{edges} & \multicolumn{1}{|c|}{density} & \multicolumn{1}{|c|}{max clique} & \multicolumn{1}{|c|}{CP-alg} & \multicolumn{1}{|c||}{PR-alg} \\ \hline 6 & 2 & 64 & 1824 & 90 & 32 & 13.170 & 6.872\\ 6 & 3 & 64 & 1344 & 67 & 8 & 0.490 & 4.694 \\ 6 & 4 & 64 & 704 & 35 & 4 & 0.080 & 0.338 \\ 6 & 5 & 64 & 224 & 11 & 2 & 0.060 & 0.0116 \\ 7 & 3 & 128 & 6336 & 78 & 16 & 307.388 & 2576.500 \\ 7 & 4 & 128 & 4096 & 50 & 8 & 1.532 & 21.640 \\ 7 & 5 & 128 & 1856 & 23 & 2 & 0.176 & 1.078 \\ 8 & 2 & 256 & 31616 & 97 & 79\footnote{This is a lower bound, calculated at termination.} & $> 10^{5}$ & $> 10^{5}$ \\ 8 & 4 & 256 & 20864 & 64 & 16 & 1029.970 & $> 10^{5}$\\ \hline \end{tabular} \end{minipage} \caption{Computational results on Hamming graphs} \label{tb:hamm} \end{table} In table~\ref{tb:john} the values of binary vector size, vector weight and Hamming distance for the Johnson graphs are given in the first three columns. Notable here is that the CP-algorithm is the fastest even when the density is rather high. \begin{table}[h] \centering \scriptsize \begin{tabular}{||r|r|r|r|r|r|r|r|r||} \hline \multicolumn{9}{|c|}{Computational results for Johnson graphs} \\ \hline \hline & & & \multicolumn{1}{c|}{number of} & \multicolumn{1}{c|}{number of} & \multicolumn{1}{c|}{graph} & \multicolumn{1}{c|}{size of} & \multicolumn{2}{c|}{Avg CPU-time {\tiny (sec)}} \\ \cline{8-9} \multicolumn{1}{||c|}{n} & \multicolumn{1}{|c|}{w} & \multicolumn{1}{|c|}{dist} & \multicolumn{1}{|c|}{vertices} & \multicolumn{1}{|c|}{edges} & \multicolumn{1}{|c|}{density} & \multicolumn{1}{|c|}{max clique} & \multicolumn{1}{|c|}{CP-alg} & \multicolumn{1}{|c||}{PR-alg} \\ \hline 8 & 3 & 4 & 56 & 1120 & 73 & 8 & 0.808 & 7.190\\ 8 & 3 & 6 & 56 & 280 & 18 & 2 & 0.050 & 0.022\\ 8 & 4 & 4 & 70 & 1855 & 77 & 14 & 2.334 &14.724\\ 8 & 4 & 6 & 70 & 595 & 25 & 2 & 0.070 & 0.228\\ 9 & 3 & 4 & 84 & 2730 & 78 & 12 & 26.694 & 229.760\\ 9 & 3 & 6 & 84 & 840 & 24 & 3 & 0.090 & 0.366\\ 10 & 3 & 6 & 120 & 2100 & 29 & 3 & 0.214 & 3.064\\ 11 & 2 & 4 & 55 & 990 & 67 & 5 & 0.360 & 5.188\\ 12 & 2 & 4 & 66 & 1485 & 69 & 6 & 1.068 & 18.067\\ 13 & 2 & 4 & 78 & 2145 & 71 & 6 & 4.500 & 101.410\\ 14 & 2 & 4 & 91 & 3003 & 73 & 7 & 15.538 & 356.480\\ 15 & 2 & 4 & 105 & 4095 & 75 & 7 & 74.844 & 2145.660\\ 16 & 2 & 4 & 120 & 5460 & 76 & 8 & 278.162 & 7880.820\\ \hline \end{tabular} \caption{Computational results on Johnson graphs} \label{tb:john} \end{table} The results on Keller graphs $\Gamma_{n}$ are presented in table~\ref{tb:kell}. Here $n$ denotes the vector size. Since the size of these graphs is $4^n$ for given $n$, we are not able to solve problems with $n > 4$. \begin{table}[h] \centering \scriptsize \begin{tabular}{||r|r|r|r|r|r|r||} \hline \multicolumn{7}{|c|}{Computational results for Keller graphs} \\ \hline \hline & \multicolumn{1}{c|}{number of} & \multicolumn{1}{c|}{number of} & \multicolumn{1}{c|}{graph} & \multicolumn{1}{c|}{size of} & \multicolumn{2}{c|}{Avg CPU-time {\tiny (sec)}} \\ \cline{6-7} \multicolumn{1}{||c|}{n} & \multicolumn{1}{|c|}{vertices} & \multicolumn{1}{|c|}{edges} & \multicolumn{1}{|c|}{density} & \multicolumn{1}{|c|}{max clique} & \multicolumn{1}{|c|}{CP-alg} & \multicolumn{1}{|c||}{PR-alg} \\ \hline 3 & 64 & 1088 & 54 & 5 & 0.200 & 1.952\\ 4 & 256 & 21888 & 67 & 12 & 6302.600 & $> 10^{5}$\\ \hline \end{tabular} \caption{Computational results on Keller graphs} \label{tb:kell} \end{table} \begin{table}[h] \scriptsize \centering \begin{minipage}{9.5cm} \begin{tabular}{||r|r|r|r|r|r||} \hline \multicolumn{6}{|c|}{Computational results for Sanchis graphs} \\ \hline \hline \multicolumn{1}{||c|}{number of} & \multicolumn{1}{c|}{number of} & \multicolumn{1}{c|}{graph} & \multicolumn{1}{c|}{size of} & \multicolumn{2}{c|}{avg CPU-time {\tiny (sec)}} \\ \cline{5-6} \multicolumn{1}{||c|}{vertices} & \multicolumn{1}{|c|}{edges} & \multicolumn{1}{|c|}{density} & \multicolumn{1}{|c|}{max clique} & \multicolumn{1}{|c|}{CP-alg} & \multicolumn{1}{|c||}{PR-alg} \\ \hline 50 & 245 & 20 & 5 & 0.048 & 0.870\\ 50 & 613 & 50 & 5 & 0.096 & 0.590\\ 50 & 980 & 80 & 5 & 1.396 & 26.952\\ 90 & 597 & 15 & 5 & 0.088 & 0.320\\ 90 & 2003 & 50 & 5 & 0.646 & 12.592\\ 90 & 3204 & 80 & 5 & 30.160 & 841.360\\ 90 & 3204 & 80 & 5 & $30.220^{a}$ & $852.300^{a}$ \\ 130 & 1677 & 20 & 10 & 0.200 & 0.988\\ 130 & 4193 & 50 & 10 & 1.299 & 20.440\\ 130 & 4193 & 50 & 10 & $1.725^{a}$ & $18.780^{a}$ \\ 130 & 6708 & 80 & 10 & $> 3600$ & $> 3600$\\ \hline \end{tabular} \footnotetext[1]{Calculated on randomly relabeled graphs} \end{minipage} \caption{Computational results on Sanchis graphs} \label{tb:sanc} \end{table} In table~\ref{tb:sanc} we present the results we obtained by testing the two algorithms on the complement of graphs generated for the vertex cover problem. Both algorithms are efficient when the density is low. However, both algorithms have difficulties for dense graphs. Recall that the graphs are generated in such a way that the first node is always in the maximum clique. Thus, one might suspect that the labeling of the nodes of these graphs makes them easy to test. For this reason, for each test graph, we repeated the experiment with randomly relabeled nodes. It turns out that there is no notable difference in CPU time. \section{Concluding Remarks} In this paper we presented a variety of test cases for the maximum clique problem. The generated graphs can be used to test and compare proposed algorithms for the maximum clique problem. Also, we discussed the generation of graphs with known maximum clique size (see also \cite{Par}). All Fortran codes of the test generators are available by {\it e-mail} from {\it pardalos@math.ufl.edu} or {\it vairakta@ise.ufl.edu}. \setlength{\baselineskip}{.66\baselineskip} \begin{thebibliography}{100} \bibitem{BX} Balas, E. and J. Xue, Minimum Weighted Coloring of Triangulated Graphs, with Application to Maximum Weight Vertex Packing and Clique Finding in Arbitrary Graphs, {\it SIAM J. Computing} 20(2):209-221, 1991. \bibitem{BY} Balas, E. and C.S. Yu, Finding a Maximum Clique in an Arbitrary Graph, {\it SIAM J. Computing} 14(4):1054-1068, 1986. \bibitem{Ber} Berman P. and A. Pelc, Distributed Fault Diagnosis for Multiprocessor Systems, {\it Proc. of the 20th Annual Intern. Symp. on Fault-Tolerant Computing} (Newcastle, UK) 340-346, 1990. \bibitem{Blo} Blough D. M., Fault Detection and Diagnosis in Multiprocessor Systems, {\em Ph.D. Thesis, The John Hopkins University}, 1988. \bibitem{Bro} Brouwer, A. E., J. B. Shearer, N. J. A. Sloane and W. D. Smith, A New Table of Constant Weight Codes. {\it IEEE Transactions on Information Theory} 36(6):1334-1380, 1990. \bibitem{CP} Carraghan R. and P.M. Pardalos, An Exact Algorithm for the Maximum Clique Problem, {\it Operations Research Letters} 9:375-382, 1990. \bibitem{Cor} Corr$\acute{a}$di K. and S. Szab$\acute{o}$, A combinatorial approach for Keller's conjecture, {\it Periodica Math. Hung.} 21(2):95-100, 1990. \bibitem{Haj} Haj$\acute{o}$s G., Sur la factorisation des abeliens, {\it Casopis} 74:189-196, 1950. \bibitem{KE} Keller O. H., $\ddot{U}$ber die l$\ddot{u}$ckenlose Erf$\ddot{u}$llung des Raumes mit W$\ddot{u}$rfeln, {\it J. Reine Angew. Math.} 163:231-248, 1930. \bibitem{Lag} Lagarias J. C., P. W. Shor, Keller's Cube-Tiling Conjecture is False in High Dimensions. {\it Bulletin AMS} 27(2):279-283, 1992. \bibitem{WS} MacWilliams F. J. and N. J. A. Sloane, The Theory of Error-Correcting Codes. {\it North Holland, Amsterdam} 1979. \bibitem{Par} Pardalos P.M., Construction of Test Problems in Quadratic Bivalent Programming, {\it ACM Transactions on Mathematical Software} 17(1):74:87, 1991. \bibitem{PR} Pardalos P.M. and G.P. Rodgers, A Branch and Bound Algorithm for the Maximum Clique Problem, {\it Computers and Operations Research} 19(5):363-375, 1992. \bibitem{PV} Pardalos P. M. and G. Vairaktarakis, Test Cases for the Maximum Clique Problem, {\it COAL Bulletin} 21:19-23, 1992. \bibitem{PX} Pardalos P. M. and J. Xue, The Maximum Clique Problem, {\em Manuscript, University of Florida}, (August 1992). \bibitem{Per} Perron O., $\ddot{U}$ber l$\ddot{u}$ckenlose Ausfullung des n-dimensionalen Raumes durch kongruente W$\ddot{u}$rfel, {\it Math. Z.} 46:1-26,161-180, 1940. \bibitem{PMC} F. P. Preparata, G. Metze and R. T. Chien, On the Connection Assignment Problem of Diagnosable Systems, {\em IEEE Trans. Electr. Comput.}, 16: 848--854 (1967). \bibitem{San1} Sanchis L., Test Case Construction for the Vertex Cover Problem (extended abstract), {\it DIMACS Workshop on Computational Support for Discrete Mathematics}, March 1992. \bibitem{San2} Sanchis L., Test Case Construction for NP-hard problems (extended abstract), {\em Proceedings of the 26th Annual Allerton Conference on Communication, Control, and Computing}, September 1988. \bibitem{Slo} Sloane N. J. A., Unsolved Problems in Graph Theory Arising from the Study of Codes. {\it Graph Theory Notes of New York XVIII} 11-20, 1989. \bibitem{ST} Stein S. K., Algebraic tiling, {\it Amer. Math. Monthly} 81:445-462, 1974. \bibitem{SZ} Szab$\acute{o}$ S., A reduction of Keller's conjecture, {\it Periodica Math. Hung.} 17(4):265-277, 1986. \bibitem{X} Xue J., Fast Algorithms for Vertex Packing and Related Problems, {\it Ph.D. Thesis} GSIA, Carnegie Mellon University, 1991. \end{thebibliography} \end{document}