Minimum Coloring Random and Semi-Random Graphs in Polynomial Expected Time

We present new algorithms for k-coloring and minimum (x(G)-) coloring random and semi-random k- colorable graphs in polynomial expected time. The random graphs are drawn from the G(n,p, k) model and the semi-random graphs are drawn from the $G_{SB}(n,p,k)$ model. In both models, an adversary initially splits the n vertices into K color classes, each of size $\Theta(n)$. Then the edges between vertices in different color classes are chosen one by one, according to some probability distribution. The model $G_{SB}(n,p,k)$ was introduced by Blum [3] and with respect to randomness, it lies between the random model G(n,p,k) where all edges are chosen with equal probability and the worst-case model. This extended abstract consists of two parts. In Part I, we propose a general methodology for designing algorithms for k-coloring random graphs from G(n,p,k). Using this, we derive new algorithms for k-coloring $G \in G(n,p,k)$ for $p\geq n^{-1+\epsilon}$ where E is any constant greater than 1/4. Our algorithms run in polynomial time on the average. This improves the results of [13] where \epsilon was required to be above 0.4. In Part II, we present polynomial average time algorithms for minimum coloring semi-random graphs from $G_{SB}(n,p,k)$ for $p \geq n^{-\alpha(k)+\epsilon}$, where \alpha(k) = (2IC)/((k - l)(k + 2)) and E is any positive constant. We also present polynomial average time algorithms for X(G)-coloring random graphs from G(n,p,k), with $p \geq n^{-\gamma(k)+\epsilon}$ where $\gamma(k) = (2k)/(k^2 - k + 2)$. The problem of X(G)-coloring is harder than the k-coloring problem because every k-colorable graph has a ”short certificate” for k-colorability, but there are many k-colorable graphs with x(G) = k for which there is no known short certificate for the fact x(G) = k