Culberson's Graph Coloring Research

Randomized Approaches to NP-Complete Problems

Graph Coloring and Clique finding are two NP-complete optimization problems which are also known, by recent results, to be hard to approximate. On the other hand, it is also known that for a graph drawn at random from all n-vertex graphs, the simple greedy algorithm will yield a coloring within a factor of two with high probability. Iterative techniques can do much better in reasonable time.

This research focuses on the two-sided approach of trying to find better iterative and heuristic algorithms, and to determine the limits of these approaches over various classes of graphs. For this latter objective, it is useful to determine classes of graphs which thwart these and most other algorithms.

In coloring, TR92-07: Iterated Greedy Graph Coloring and the Difficulty Landscape surveys some previous coloring approaches, describes my Iterated Greedy Approach, and surveys the landscape of k-colorable graphs using a mixture of approaches. Also available is a searchable bibliography of coloring and clique related references in bibtex format and also in compressed postscript format. I welcome additional references, and error corrections; these should be sent to joe@cs.ualberta.ca .

In a paper presented at the DIMACS for the Second Challenge on Cliques, Graph Coloring and Satisfiability, co-authored with Feng Luo, and titled Exploring the k-colorable Landscape with Iterated Greedy we extended the experimental results and the classes of graphs to ones with up to ten thousand vertices. At the same workshop, Mark Brockington presented joint work on the difficulty of hiding independent sets in graphs Camouflaging Independent Sets in Quasi-Random Graphs.

See also Mike Trick's site Second Challenge.

As with many such problems, the difficult instances in graph coloring seem to be found mostly on a narrow ``ridge'' of graphs with particular properties. Current research is focused on better understanding the structures and qualities that make up the graphs found in this region of graph space.

A study looking for harder classes of graphs was presented at the CP95 Workshop on Studying and Solving Really Hard Problems held September 23, 1995 in Cassis, France. This paper, Hiding our colors co-authored with Adam Beacham and Denis Papp, presents first results from a generating program available here. (The paper is also available via ftp://ftp.cs.ualberta.ca/pub/joe/Preprints/ssrhpclr.ps.gz). This program generates graphs which have a hidden $k$-coloring.

Joseph Culberson

Nov 21, 1995