Frozen development in graph coloring

J Culberson, I Gent

Research output: Contribution to journalArticlepeer-review

81 Citations (Scopus)

Abstract

We define the 'frozen development' of coloring random graphs. We identify two nodes in a graph as frozen if they are of the same color in all legal colorings and define the collapsed p graph as the one in which all frozen pairs are merged. This is analogous to studies of the development of a backbone or spine in SAT (the Satisfiability problem). We first 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. This applies even where this probability is infinitesimal such as 10(-300), although our estimates might be subject to very high variance. 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 are 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 becomes 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. (C) 2001 Elsevier Science BY. All rights reserved.

Original languageEnglish
Pages (from-to)227-264
Number of pages38
JournalTheoretical Computer Science
Volume265
Issue number1-2
DOIs
Publication statusPublished - 28 Aug 2001

Keywords

  • threshold phenomena
  • graph coloring
  • backbone
  • spine
  • frozen development
  • PHASE-TRANSITION
  • HARD
  • SATISFACTION
  • NUMBER

Fingerprint

Dive into the research topics of 'Frozen development in graph coloring'. Together they form a unique fingerprint.

Cite this