algorithms for coloring random and semi-random graphs

Abstract

The graph coloring problem is NP-hard and arises in a variety of practical situations. Recent breakthroughs in the area of approximation complexity indicate that it is not possible (unless P = NP) even to approximate the chromatic number of a graph within a constant ratio. However, the worst-case complexity takes a pessimistic approach and requires the algorithm to perform well on all input graphs. Instead, if we require that the algorithm perform well on “most” of the input graphs, then it is possible to design polynomial-time algorithms for coloring graphs. We present polynomial-time almost surely succeeding algorithms and polynomial average-time algorithms for coloring graphs from two different models of random graphs denoted G(n, p, k) and GsB(n, p, k). The GsB(n, p, k) model is called a semi-random model, and in terms of randomness, it lies between the random model G(n, p, k) and the worst-case model. Our results significantly improve all the previously known results for this problem. We have obtained the following results:

Let G ? G(n, p(n), k) be a random graph with p(n) > ?, where ? is any positive constant greater than 1/4. Then there exists a polynomial-time algorithm for k-coloring G with exponentially low failure probability. Let G ? G(n, p(n), k) be a random graph with p(n) > ? for some positive constant ? and p(n) < ?(log n), for some positive integer ? > 3. Then there exists a polynomial-time algorithm for k-coloring G with exponentially low failure probability. Let G ? GsB(n, p(n), k) be a semi-random graph with p(n) > ?(k), where ?(k) = (2k)/((k ? 1)(k + 2)) and ? is any positive constant. Then there exists a polynomial-time algorithm for k-coloring G with exponentially low failure probability. Let G ? G(n, p(n), k) be a random graph with p(n) > ?, where ? is any positive constant greater than 1/4. Then G can be k-colored in polynomial average time. Let G ? G(n, p(n), k) be a random graph with p(n) > ?(k), where ?(k) = (2k)/((k² ? k ? 2)), and ? is any positive constant. Then a ?(G)-coloring of G can be found in polynomial average time. Let G ? GsB(n, p(n), k) be a semi-random graph with p(n) > ?(k), where ?(k) = (2k)/((k ? 1)(k + 2)), and ? is any positive constant. Then a ?(G)-coloring of G can be found in polynomial average time.

Our algorithms also work over graphs drawn from random models in which each vertex is assigned one of the k colors uniformly randomly.