\documentstyle{article}
\title{DIMACS Challenge abstract}
\author{Lud\v ek Ku\v cera
\thanks{On leave from Charles University, Prague, {\tt kuceral@cspguk11.bitnet}}
\\
Max Planck Institut f\"ur Informatik\\
Saarbr\"ucken\\
{\tt kucera@mpi-sb.mpg.de}}

\begin{document}
\maketitle

The contribution to the Challenge will be directed to the coloring algorithms, and also to clique algorithms, because they use quite often similar techniques.

The Challenge (more precisely its coloring part) is a call for the best coloring algorithm. However, (certainly unless P=NP is solved), no algorithm can be claimed the {\em best} in the absolute sense. The challenge activity is therefore a kind of olympics, where disciplines are represented by input generating procedures, and for each of them the winner is selected among participating algorithms, based on the time, precision or other criterion.

Input generating procedures can be either deterministic or randomized. We will concentrate to {\em probabilistic methods of generating graphs that are difficult to color}, and also to algorithms that behave (or are conjectured to behave) well on such inputs.

As an example, consider the following input distibution: given natural numbers $n$, $k$ such that $k>>\sqrt{n}$, select uniformly at random a $k$-colorable graph with $n$ vertices. It seems to be difficult to find a $k$-coloring of such a graph by a polynomial time algorithm. However, there is an $n^{O(\log n)}$ algorithm, which is optimal almost surely. It is therefore interesting, how large the parameters $n$, $k$ can be when we want to find a $k$-coloring efficiently. This distribution can be approximate by another one, that can be generated efficiently by a polynomial time randomized procedure. For more details, see references Turner [80], Ku\v cera [60-62], Dyer and Frieze [34] of the Challenge review.

Our main goal is to find efficient randomized input generators such that known algorithm would not be able to find a good approximization the optimal solution in a sufficiently short time.
\end{document}