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