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


