\documentstyle[12pt]{article}
% \input{my_environment}
% -------------- begin environment ---------------------

% A single file version of environment
% \input {math_macros}

% Book Mathematical Macros

\newcommand {\implies}         {\Longrightarrow}
\newcommand {\suchthat}        {\ni}
\newcommand {\thereexists}     {\exists}
\newcommand {\therexists}      {\exists}
\newcommand {\foralldistinct}  {\forall \mbox{ distinct }}
\newcommand {\tendsto}         {\to}
\newcommand {\elementof}       {\in}
\newcommand {\infinity}        {\infty}
\newcommand {\subsetof}        {\subseteq}

\newcommand {\union}           {\cup}
\newcommand {\intersect}       {\cap}
\newcommand {\intersection}    {\cap}
\newcommand {\composition}     {\wedge}
\newcommand {\setdifference}   {\setminus}

\newcommand {\bigunion}        {\bigcup}
\newcommand {\bigintersection} {\bigcap}
\newcommand {\bigcomposition}  {\bigwedge}

\newcommand {\setdelim}        {\; | \;}
\newcommand {\degrees}         {^\circ}
\newcommand {\qed}             {\rule{1ex}{1ex}}

\renewcommand {\emptyset}      {\mbox{\O}}

\newcommand {\r}               {\mbox{$\Re$}}
\newcommand {\rtwo}            {\mbox{$\Re^2$}}
\newcommand {\rn}              {\mbox{$\Re^n$}}

\newcommand {\flogn}           {{\lfloor \lg n \rfloor}}
\newcommand {\clogn}           {{\lceil \lg n \rceil}}
\newcommand {\fntwo}           {{\lfloor n / 2 \rfloor}}
\newcommand {\cntwo}           {{\lceil n / 2 \rceil}}

\newcommand {\smsp}            {\; ; \;}
\newcommand {\medsp}           {\; \;}
\newcommand {\bigsp}           {\; \; \; \;}

\renewcommand {\sp}            {\; , \; \; \;}

\newcommand {\mod}             {\bmod}

\newcommand {\N}               {\mbox{\bf N}}
\newcommand {\R}               {\mbox{$\Re$}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% PhD Mathematical Macros

\newcommand {\parallelto}      {\parallel}

\newcommand {\hull}            {\mbox{-} hull}
\newcommand {\conjugate}       {\mbox{-} conjugate}
\newcommand {\closure}         {\mbox{-} closure}
\newcommand {\region}          {\mbox{-} \|}
\newcommand {\kernel}          {\mbox{-} kernel}

\newcommand {\RO}              {\mbox{${\cal O}$}}
\newcommand {\C}               {\mbox{${\cal C}$}}
\newcommand {\LS}              {\mbox{${\cal LS}$}}
\newcommand {\Q}               {\mbox{${\bf Q}$}}

\renewcommand {\L}             {\mbox{${\cal L}$}}
\renewcommand {\H}             {\mbox{${\cal H}$}}
\renewcommand {\P}             {\mbox{${\bf P}$}}
\renewcommand {\S}             {\mbox{${\cal S}$}}

% \input {program_macros}

% Programming Macros

\newcommand {\exchange} {\leftrightarrow}

% \input {math_envs}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Mathematical Environments

\newtheorem{theorem}{{\sc Theorem}}[section]
\newtheorem{conjecture}{{\sc Conjecture}}[section]
\newtheorem{lemma}{Lemma}[section]
\newtheorem{corollary}{Corollary}[section]

\newenvironment{proof}{\noindent{\bf Proof:}}{$\qed$ \medskip}

\newenvironment{remark}{\medskip \noindent Remark:}{\medskip}
\newenvironment{definition}{\medskip \noindent Definition:}{\medskip}
\newenvironment{observation}{\medskip \noindent \bf Observation:}{\medskip}
\newenvironment{property}{\medskip \noindent Property:}{\medskip}
\newenvironment{proposition}{\medskip \noindent Proposition:}{\medskip}

% \input {problem_envs}

% Problem Environments

\newenvironment{pause}{\begin{ssf}\paragraph*{\fbox{Pause}}}{\end{ssf}\bigskip}

\newenvironment{exercise}{\begin{ssf}\paragraph*{\fbox{Exercise \addtocounter{ex}{1}\arabic{chapter}.\arabic{section}.\arabic{ex}}}}{\end{ssf}\bigskip}

\newenvironment{problems}{\begin{ssf}\subsection*{\fbox{Problem Set \arabic{chapter}.\arabic{section}}}}{\end{ssf}}

\newenvironment{deepend}{\begin{ssf}\section*{\fbox{The Deep End}}}{\end{ssf}}

\def\boxit#1{\vbox{\hrule\hbox{\vrule\kern3pt\vbox{\kern3pt#1\kern3pt}\kern3pt\vrule}\hrule}}

\newenvironment{procedure}{
\begin{minipage}{5in}
\begin{tabbing}
1234\=1234\=1234\=1234\=1234\=1234\=1234\=1234\=1234\=\kill
}{
\end{tabbing}
\end{minipage}
}

% \newcommand{\procdisp}[1]{
% \center{\fbox{
% \begin{minipage}{5in}
% \begin{tabbing}
% 1234\=1234\=1234\=1234\=1234\=1234\=1234\=1234\=1234\=\kill
% {#1}
% \end{tabbing}
% \end{minipage}
% }}}
\newcommand{\procbegin}{\typeout{ERROR:::::::::::::
procbegin REPLACED by environment procedure.
To box, precede use by center and fbox and follow by closing braces}}

% \input {boxit}

\def\boxit#1{\vbox{\hrule\hbox{\vrule\kern3pt\vbox{\kern3pt#1\kern3pt}\kern3pt\vrule}\hrule}}

% \input {Defs}
%\setcounter{topnumber}{99}
%\renewcommand{\topfraction}{.999}
%\setcounter{bottomnumber}{99}
%\renewcommand{\bottomfraction}{.999}
%\setcounter{totalnumber}{99}
%\renewcommand{\textfraction}{.001}
%\renewcommand{\floatpagefraction}{.001}

\newcommand{\putfig}[2]{%
	\begin{figure}%
		\begin{center}%
			\input{figures/#1}%
			\usebox{\graph}%
			\caption{#2\label{#1}}%
		\end{center}%
	\end{figure}%
}%

\newcommand{\puttab}[2]{%
	\begin{table}%
		\begin{center}%
			\input{tables/#1}%
			\caption{#2\label{#1}}%
		\end{center}%
	\end{table}%
}%

\newcommand{\sectdef}[3]{%
	\ifcase #1%
		\typeout{Section depth #1 undefined; 1 used instead.}%
		\section{#3\label{sect.#2}}%
	\or	\section{#3\label{sect.#2}}%
	\or	\subsection{#3\label{sect.#2}}%
	\or	\subsubsection{#3\label{sect.#2}}%
	\or	\paragraph{#3\label{sect.#2}}%
	\or	\subparagraph{#3\label{sect.#2}}%
	\else%
		\typeout{Section depth #1 undefined; 1 used instead.}%
		\section{#3\label{sect.#2}}%
	\fi%
}%

\newcommand{\figdef}[2]{figure~\ref{fig.#1}\putfig{#1}{#2}}%
\newcommand{\Figdef}[2]{Figure~\ref{fig.#1}\putfig{#1}{#2}}%
\newcommand{\tabdef}[2]{table~\ref{tab.#1}\puttab{#1}{#2}}%
\newcommand{\Tabdef}[2]{Table~\ref{tab.#1}\puttab{#1}{#2}}%

\newcommand{\fig}[1]{figure~\ref{#1}}%
\newcommand{\Fig}[1]{Figure~\ref{#1}}%
\newcommand{\tab}[1]{table~\ref{#1}}%
\newcommand{\Tab}[1]{Table~\ref{#1}}%
\newcommand{\sect}[1]{section~\ref{#1}}%
\newcommand{\Sect}[1]{Section~\ref{#1}}%

\newcommand{\references}[1]{%
	\bibliographystyle{#1}%
	\bibliography{/usr/home/prof/joe/Tex/Biblib/defs-#1,%
		/usr/home/prof/joe/Tex/Biblib/references}%
}%
% ------------ end environment ---------------------

\newcommand{\SM}{\mbox{\rm SM}}
\newcommand{\half}{{1 \over 2}}
\newcommand{\gc}[1]{{\cal{G}}_{#1}}
\newcommand{\dgc}{\gc{n,p}}
\newcommand{\bre}{Br\'{e}laz}


%  ******** STARTS HERE ***************


\begin{document}
\title{Hiding in Graphs: A Proposal}
\author{
Mark Brockington
\thanks{
email brock@cs.ualberta.ca
Supported by Natural Sciences and Engineering Research Council
Postgraduate Scholarship PGS A156882}
\and
Joseph C. Culberson
\thanks
{
(for further info contact) email:joe@cs.ualberta.ca 
Supported by Natural Sciences
and Engineering Research Council Grant No. OGP8053.
Department of Computing Science, University of Alberta,
Edmonton, Alberta, Canada, T6G 2H1.
}
\and 
Peter VanBeek
\thanks
{
email:vanbeek@cs.ualberta.ca
Supported by Natural Sciences
and Engineering Research Council Grant No. OGP105446.
Department of Computing Science, University of Alberta,
Edmonton, Alberta, Canada, T6G 2H1.
}
}
\maketitle
\begin{abstract}
Recently it has been shown that unless $\mbox{\rm P} = \mbox{\rm NP}$,
no polynomial time algorithms exist which can, in the worst case,
approximate the Maximum Independent set or the optimal coloring of
a graph within a factor of $O(n^{\epsilon})$ for some $\epsilon > 0$.

In this note we observe that the most common methods of generating
graphs with known maximal independent sets or specified colorings
are subject to attack using
quite simple techniques that are successful significantly
often for graphs of practical size.

We propose to look at the problem of how one might try to hide a 
large independent set in a graph in which all other independent sets are 
significantly smaller.
We will also look at the problem of hiding a coloring 
significantly smaller than any other coloring of a graph.
\end{abstract}

\section{Introduction}

In \cite{cl:kuc91} a graph with an independent set of size $s$ is
created given a probability distribution on edges such that the
probability of a set larger than $s-1$ is small.  The basic algorithm is
to select a set $I$ of $s$ vertices and for each pair of vertices
$x,y$, if $x,y \in I$ then no edge is assigned, otherwise $\{x,y\}$ is
an edge with (independent) probability $p$.
We call this the {\em naive set creation} (NSC) algorithm.

Preliminary experiments show that for $n=1000$ these can be
found with high probability (at least higher than one would want for
cryptographic systems).  The basic algorithm, $\SM^0$ is fairly standard
and presented in \fig{figsm0}.

\begin{figure}[hbpt]
\center{\fbox{
\begin{procedure}
INPUT: $G = (V,E)$\\
OUTPUT: A maximal independent set $I$ \\
\> $Z = V$ \\ 
\> $I = \emptyset$ \\ 
\> while $Z \ne \emptyset $ do \\ 
\> \> Select $v \in Z$ of minimum degree \\ 
\> \> $I = I \union \{v\}$\\ 
\> \> $Z = Z - \{v\} - N(v)$ \\ 
\> end \\
\> return $I$ \\
\end{procedure}
}}
\caption{Algorithm $\SM^0$}
\label{figsm0}
\end{figure}

$N(v)$ indicates the neighbors of the vertex $v$ in $G$.
This algorithm, $\SM^0$, is not very effective for 1000 node graphs
for finding sets hidden by the NSC algorithm.
$\SM^0$ can be implemented to run in $O(n^2)$ time.  

$\SM^i$ for
$i = 1,2,\dots$ are algorithms in which every combination of $i$
vertices (which form independent sets) are generated and extended using
$\SM^0$. A more formal statement is given in \fig{figsmi}.
(Here $N(I_0)$ means the union of the neighbors of the vertices in $I_0$.)
$\SM^i$ runs in $O(n^{i+2})$ time for fixed $i$.
\begin{figure}[hbpt]
\center{\fbox{
\begin{procedure}
INPUT: $G= (V,E)$\\
OUTPUT: A maximal independent set $I$ \\
\> $I = \emptyset$\\
\> $\forall I_0 \subseteq V$, $|I_0| = i$ \\
\> \> If $I_0$ is an independent set then \\
\> \> \> Compute the induced subgraph $G'$ with vertex set \\
\> \> \> \> $V' = V - I_0 - N(I_0)$\\
\> \> \> $I = \max\{I, I_0 \union \SM^0(G')\}$ \\
\> end \\
\> return $I$\\
\end{procedure}
}}
\caption{Algorithm $\SM^i$}
\label{figsmi}
\end{figure}

For $n=1000$ and using the minimum probability $p$ allowed by the
criteria set by \cite{cl:kuc91}, $\SM^2$ found the independent set 16\% of
fifty trials. As $p$ goes to $\half$, the success
frequency greatly increased.

We will look at this problem and then will consider
whether it is possible to define a class of graphs resistant to this
line of attack, with the requirement 
that there is a significant difference in the size of the
maximum independent set and the one likely to be found.

We can improve $\SM^0$ by allowing it to do one or two backtracks 
over the selection of $v$, subject to some limits to prevent too much time being
taken (e.g. two or three branches only at the first two or three levels
of expansion).
To speed up the running time,
$\SM^i$ does not need to look at all ${n \choose i}$
subsets. If we use a backtrack algorithm for selecting these subsets,
we can limit the branching factor to some portion of the vertices
for the $i$th vertex and still have a high
probability of finding an $i$-subset of the created independent set $I$.
The subgraph passed to $\SM^0$ will be of expected size 
$\approx {n  {(1-p)^i}}$ and so allowing some backtrack in $\SM^0$
can be done in reasonable time.

Algorithms such as the one used by Bollob\'{a}s and Thomason
\cite{cl:both85} are powerful generalizations of this
notion which do partial backtrack. They report finding independent sets of size
15 in $\gc{1000,\half}$, which is the maximum expected with high probability.
In \cite{cl:cul92a} a modified version of this algorithm 
regularly found independent sets of size 15.
Using the NSC,
with $p=\half$ and a created independent set of size 16, even $\SM^2$ had a high
success rate.

\section{Why the Attack Works}
Let us define $s = |I|$, and let $S_i$ of size $i$ be a (random) subset of $I$.
Let $I_i = I - S_i$ and thus $I_0 = I$. 
The vertices which are independent of $S_i$ are
$V_i = V - S_i - N(S_i)$, where
$N(S_i)$ is the union of the neighborhoods of vertices in $S_i$, 
$\bigcup_{v \in S_i} N(v)$.

We let $\mu(I_i)$ be the average degree of a vertex in $I_i$ in the subgraph
induced by $V_i$, and $\mu(\bar{I}_i)$ the average degree of a vertex 
in $V_i - I_i$. 
Similarly, we use $\sigma$ as the standard deviation (assuming
the expected number of nodes).
We say that $I_i$ {\em stands out} if the difference 
$d_i = \mu(\bar{I}_i) - \mu(I_i) \ge \sigma(\bar{I}_i)$.
The idea is that if $I_i$ stands out, selecting a vertex
on the basis of degree has a 
reasonably high chance of choosing a vertex from $I_i$.
This means we have a reasonable chance of finding the independent set $I$
once we have found a set $S_i$.
If $I_i$ stands out, $\SM^i$ then has a reasonable chance of finding $I$
because it will find every subset of size $i$ of $I$.

Note that we have implicitly defined what we mean by {\em reasonable chance}.
For security purposes, we would want to be able to hide so that a search
had a far less than reasonable chance, while for a practical algorithm we might
wish for something better.
However, this gives a working definition,
from which we can hope to learn something of how difficult it is to hide.

Suppose we have created a graph using probability $p$ on $n$ vertices with
$s=|I|$, where we may assume that $I$ is larger than the probable
size of a maximum independent set in a graph in $\gc{n,p}$.
Then $\mu(I) = (n-s)p$, $\mu(\bar{I}) = (n-1)p$, $d_0 = (s-1)p$ and
$\sigma(\bar{I}) = \sqrt{(n-1)p(1-p)}$.
Thus, if $p= \half$, $n=1000$, we see that with $s \ge 31$ the independent set
will stand out.
It is well known \cite{cl:man85} that with high probability the maximum
independent set of a graph in $\gc{1000,\half}$ will be of size 15 or less.
So for this case a set created by NSC
will stand out at $i=0$ if the set is twice the
background.

Noting that $|I_i| = s-i$ and the expected size of $\bar{I}_i$ is 
$(n-s)(1-p)^i$, we see that $\mu(I_i) = p(n-s)(1-p)^i$
and $\mu(\bar{I}_i) = p((n-s-1)(1-p)^i + s -i)$.
Thus $d_i = p((s-i) - (1-p)^i) \approx p(s-i)$ and
$\sigma(\bar{I}_i) = \sqrt{(1-p)p((n-s-1)(1-p)^i + s -i)}$.
Let us suppose that NSC is used to create a hidden set of size 16 in
$\gc{1000,\half}$.
The results are shown for $i$ up to 3 in \tab{tbl1}.
\begin{table}[hbpt]
\begin{center}
\begin{tabular}{|rrr|} \hline 
$i$ & $d_i$ & $\sigma(\bar{I}_i)$ \\ \hline
0 & 7.5 & 15.68 \\
1 & 7.25 & 11.25 \\
2 & 6.88 & 8.06 \\
3 & 6.44 & 5.83 \\ \hline
\end{tabular}
\end{center}
\caption{Statistics for $s=16$ in $\gc{1000,\half}$}
\label{tbl1}
\end{table}

Although $I_2$ does not quite stand out, nevertheless $\SM^2$
found the set in 49 out of 50 trials.
Notice that for $p=\half$ this is the smallest set that we could hope to hide
and still meet the conditions in \cite{cl:kuc91}.
Or in other terms, it is the least possible ratio greater than one
of the hidden set to other sets that occur frequently.

It should be mentioned that there is another effect that helps $\SM^i$.
$I_i$ has one fewer vertex than $I_{i-1}$, while $\bar{I}_i$
has on average $(1-p)*|\bar{I}_{i-1}|$ vertices. Thus, the ratio
of desirable to undesirable vertices is increasing exponentially.

\section{Proposed Research Topic for DIMACS: Hiding Things in Graphs}

How do we embed an IS of size $ck$ in a graph so that simple techniques are
unlikely to find an IS of more than  $k$ vertices?
Recent results show that obtaining an IS within a factor of $O(n^{\epsilon})$
is NP-hard (keep in mind this is a worst case result).
Can we obtain this kind of result in {\em practice}?
This question has recently also been considered by Jagota and Regan
\cite{cl:jare92}.

% Note that $k$ cannot be a constant, since if we did a search of all 
% $k+1$ subsets, we would get a larger IS, and in particular if there is exactly
% one IS larger than $k$ we would have the $ck$-IS. This would be a polynomial
% time deterministic algorithm.
% 
% Therefore, we must let $k = k(n) \in \omega(1)$. Letting $k(n) = \log n$
% would make this approach take $n^{\log n}$ time, and thus be super-polynomial.
% However, we still need to prevent probabilistic algorithms from succeeding.

Two basic approaches (the extremes) come immediately to mind. First,
we could try to make the $ck$ sets look like $k$ sets.
Second we could try to make the $k$ sets look like the $ck$ sets.

As an example of the first approach we could try to increase the average degree
of the members of $I$ by adding a few extra edges to compensate 
for those eliminated by the construction process. 
Although this will make the degrees ``average'' initially, once a vertex is
selected from $I$ the degree problem resurfaces! 
Furthermore, we have to be a little careful since we increase slightly the
degrees of the remaining vertices. It may also be that increasing the degree
this way somehow makes the set $I$ more identifiable.

Can we add extra edges in some way to make the degrees similar even after one
or two vertices have been selected? What other avenues of attack do we open up
if this is done? (See the coloring discussion below)

As an example of the second approach we could try to eliminate edges from the
remaining vertices, while ensuring that the smaller independent sets did not
grow in size. For example, we could look at all $n \choose (k+1)$
subsets of size $k+1$ and add edges randomly to these subsets (subject to
not adding edges to the $ck$ set) so that no subset is independent.
Apart from the difficulty of how exactly to do this, this process would take
super-polynomial time and so is not practical. Furthermore, it is not
absolutely clear that this would not still leave some feature that would open
the problem to probabilistically successful randomized attacks.

For graph coloring, there is a similar problem. For 300 vertex graphs
there is a ridge of difficulty where a $k$-coloring can be specified,
but not found easily,
This ridge is quite narrow \cite{cl:cul92a}.
In approximation terms, it is much less than a factor of two
wide, i.e. we can approximate within a factor of less than two quite easily
with high probability. Even for $n=1000$, the results indicate that 
a factor of 1.4 is still about the most we can hope to hide.

Note that in this study it was found that obtaining a $k$-coloring
was harder if the specified coloring was made up of equal sized
independent sets. Usually a $k$-colorable graph is generated by
assigning colors at random to the vertices, and then making the graph compatible
with this assignment, which allows the set sizes to vary considerably
\cite{cl:jams91,cl:tur88,cl:kuc89}.

Here the Iterated Greedy algorithm finds the designated independent sets
because they again ``stand out'' from the random background.
In fact, to hide specified colorings, it seems that the 
specified independent sets must be no larger than or even smaller than
the largest naturally occurring ones.
If this follows in general, then it seems likely that as $n$ becomes large,
(but within reach of reasonable algorithms) the ratio will never be larger than
some quite small constant. 

The analysis of IG is very difficult due to the many correlations that
arise as multiple iterations occur.
However, an intuitive analysis has been attempted, and this would
suggest that IG selects the larger independent sets through a kind of
reinforcement as accidental agglomerations of vertices from the large sets
occur. Significantly, this analysis does not seem to depend on the
degree sequence,
and in fact the algorithm does not consider the degrees of the vertices.
Furthermore, the algorithm is equally effective over wide ranges of
$p$, and does not require tuning as $p$ varies, which is in contrast
to degree sensitive algorithms such as the one used in \cite{cl:both85}
and the XRLF algorithm of \cite{cl:jams91}.
Our analytic approach does appear to depend on the probability of
vertices being adjacent to the partial independent set in question.
Thus perhaps by adjusting the distributions in some way the coloring can be
made more difficult for values of $k$ further from the ridge.

It may be possible to use the IG approach to obtain single
large independent sets.
We have not yet tested this idea, but increasing the variance in the size
of the independent sets of the specified coloring seems to make the
algorithm more successful. Thus this approach might also
be useful in locating large stable sets in a degree independent 
manner.

A number of special graphs and the effectiveness of various algorithms
in dealing with them have been proposed in the past \cite{cl:jams91,cl:hpv92}.

We propose to study ways of creating graphs which are hard for
our algorithms to find good approximations to the optimal coloring or IS,
and then attempt to find improved algorithms to solve them anyway.
\begin{itemize}
\item
This research could produce useful classes of graphs for testing various
algorithms. 
\item
>From a more theoretical perspective, it could tell us something
about the difficulty of hiding things.
\item
Finally, identifying new attacks through examination of the process of
hiding things in graphs could be a useful exercise in that it could lead to new
algorithms for the general case.
\end{itemize}

We would appreciate any hints, pointers to literature or suggestions for
improvement of this study.
%\bibliographystyle{plain}
%\bibliography{/usr/home/prof/joe/Tex/Biblib/defs-plain,%
%                /usr/home/prof/joe/Research/Color/References/Texbib/color}

\begin{thebibliography}{1}

\bibitem{cl:both85}
B\'{e}la Bollob\'{a}s and Andrew Thomason.
\newblock Random graphs of small order.
\newblock In {\em Random Graphs '83}, volume~28 of {\em Annals of Discrete
  Mathematics}, pages 47--97. North-Holland Publishing Co., 1985.
\newblock Section 6: ``Colouring large random graphs''.

\bibitem{cl:cul92a}
Joseph~C. Culberson.
\newblock Iterated greedy graph coloring and the difficulty landscape.
\newblock Technical Report TR 92-07, University of Alberta Department of
  Computing Science, Edmonton, Alberta Canada T6G 2H1, 1992.
\newblock ftp ftp.cs.ualberta.ca pub/TechReports.

\bibitem{cl:hpv92}
Jonas Hasselberg, Panos~M. Pardalos, and George Vairaktarakis.
\newblock Test case generators and computational results for the maximum clique
  problem.
\newblock ftp dimacs.rutgers.edu pub/challenge/graph/contributed,
  1992.
\newblock Working Paper.

\bibitem{cl:jare92}
Arun Jagota and Kenneth~W. Regan.
\newblock Performance of max-clique approximation heuristics under
  description-length weighted distributions.
\newblock Technical report, Department of Computer Science, State University at
  New York at Buffalo, 1992.
\newblock ftp ftp.cs.buffalo.edu users/jagota or ftp dimacs.rutgers.edu
  pub/challenge/graph/contributed.

\bibitem{cl:jams91}
David~S. Johnson, Cecilia~R. Aragon, Lyle~A. McGeoch, and Catherine Schevon.
\newblock Optimization by simulated annealing: An experimental evaluation; part
  {II}, graph coloring and number partitioning.
\newblock {\em Operations Research}, 39(3):378--406, may-june 1991.

\bibitem{cl:kuc89}
Lud\u{e}k Ku\u{c}era.
\newblock Graphs with small chromatic numbers are easy to color.
\newblock {\em Information Processing Letters}, 30:233--236, 1989.

\bibitem{cl:kuc91}
Lud\u{e}k Ku\u{c}era.
\newblock A generalized encryption scheme based on random graphs.
\newblock In {\em 17th Annual Workshop on Graph-Theoretic Concepts in Computer
  Science {(WG91)}}, volume 570 of {\em Lecture Notes in Computer Science},
  pages 180--186. Springer-Verlag, Berlin, 1991.

\bibitem{cl:man85}
Bennet Manvel.
\newblock Extremely greedy coloring algorithms.
\newblock In {\em Graphs and applications (Boulder, Colo., 1982)},
  Wiley-Intersci. Pub., pages 257--270, New York, New York, 1985. John Wiley \&
  Sons, Inc.

\bibitem{cl:tur88}
Jonathan~S. Turner.
\newblock Almost all $k$-colorable graphs are easy to color.
\newblock {\em Journal of Algorithms}, 9:63--82, 1988.

\end{thebibliography}
\end{document}

