The Hardest Constraint Problems: A Double Phase Transition

Tad Hogg and Colin P. Williams
Dynamics of Computation Group
Xerox Palo Alto Research Center
Palo Alto, CA 94304
hogg@parc.xerox.com

@ARTICLE {,
 AUTHOR = "Tad Hogg and Colin P. Williams",
 TITLE = "The Hardest Constraint Problems: A Double Phase Transition",
 JOURNAL = "Artificial Intelligence",
 VOLUME = "69",
 PAGES = "359-377",
 YEAR = "1994"}

Abstract

The distribution of hard graph coloring problems as a function of graph connectivity is shown to have two distinct transition behaviors. The first, previously recognized, is a peak in the median search cost near the connectivity at which half the graphs have solutions. This region contains a high proportion of relatively hard problem instances. However, the hardest instances are in fact concentrated at a second, lower, transition point. Near this point, most problems are quite easy, but there are also a few very hard cases. This region of exceptionally hard problems corresponds to the transition between polynomial and exponential scaling of the average search cost, whose location we also estimate theoretically. These behaviors also appear to arise in other constraint problems. This work also shows the limitations of simple measures of the cost distribution, such as mean or median, for identifying outlying cases.
postcript (806K, 16 pages, available on-line only within Xerox)