|
Abstract : |
We dene the `frozen development ' of coloring random graphs. We identify two nodes in a graph as frozen if they are the same color in all legal colorings. This is analogous to studies of the development of a backbone or spine in SAT (the Satis ability problem). We rst describe in detail the algorithmic techniques used to study frozen development. We present strong empirical evidence that freezing in 3-coloring is sudden. A single edge typically causes the size of the graph to collapse in size by 28%. We also use the frozen development to calculate unbiased estimates of probability of colorability in random graphs, even where this probability is as low as 10 300. We investigate the links between frozen development and the solution cost of graph coloring. In SAT, a discontinuity in the order parameter has been correlated with the hardness of SAT instances, and our data for coloring is suggestive of an asymptotic discontinuity. The uncolorability threshold is known to give rise to hard test instances for graph-coloring. We present empirical evidence that the cost of coloring threshold graphs grows exponentially, when using either a specialist coloring program, or encoding into SAT, or even when using the best of both techniques. Hard instances seem to appear over an increasing range of graph connectivity as graph size increases. We give theoretical and empirical evidence to show that the size of the smallest uncolorable subgraphs of threshold graphs become large as the number of nodes in graphs increases. Finally, we discuss some of the issues involved in applying our work to the statistical mechanics analysis of coloring., |
