Frozen development in graph coloring.
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 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.
Introduction
A phase transition has been identied for many NP-complete problems and is
frequently correlated with a high frequency of hard instances. This contrasts
with randomly chosen instances from other regions of the problem space, where
most often such instances are easy. Recently the techniques of statistical mechanics
have been applied to the analysis of this transition, and have yielded
insights into the nature of the region and its relation to hardness. (See [9] for
an overview and many references).
One of the more recent eorts has been the identication of the nature of the
order parameter at the transition. In some problems (k-SAT, k > 2) there
is evidence that this parameter is discontinuous [16,18,19]. These problems
typically have a high frequency of hard instances. On the other hand problems
with a continuous parameter tend not to have a high frequency of hard
instances. This has been explored most thoroughly in the case of 2
[17,18]. For the Hamiltonian Cycle problem, the order parameter may also be
continuous [28] which corresponds to a very low frequency of hard instances
at the transition [26].
For SAT one measure of the order parameter is the backbone [18] which is the
number of variables that are frozen to a particular value under all satisfying
assignments. A closely related notion is the spine [2]. For k-SAT, k > 2, the
evidence indicates that this measure jumps from zero to a xed fraction of the
n variables at the transition. Parkes showed that at the satisability threshold,
many variables are frozen although some are almost free [21]. Similarly, for
Hamiltonian Cycle we can use as variables the number of edges that must
appear in all Hamiltonian Cycles of the graph. In contrast to the K-SAT case,
only a few edges are frozen in satisable instances at the transition.
For k-coloring (we consider almost exclusively) it is more di-cult to
dene and measure the order parameter, due in large part to the symmetry of
the solutions. However, it is clear that if we add an edge to a colorable graph
and it then becomes uncolorable, then in the graph without the edge the pair
of vertices must have been colored with the same color in every coloring of
the graph. Such a pair we refer to as frozen for reasons that will become
apparent in the next section. We adopt the number of such pairs as our spine,
an approximation to the order parameter for coloring, as it mimics closely the
backbone and spine used in other problems. Our spine shows strong evidence
of a discontinuous jump at the transition. We discuss some of the possible
consequences for the statistical mechanics analysis of coloring, in particular
on the likelihood of discontinuous behavior in possible order parameters.
Instances at or near thresholds are used for benchmarking algorithms in many
domains, for example satisability [15] and constraint satisfaction problems
[22,24]. However there is no simple correlation between hard instances and
phase transitions. For example, there is a classic phase transition in the solvability
of random Hamiltonian cycle instances [11] but hard instances do not
seem to be found there [25]. We provide extensive evidence that 3-coloring
problems are hard at the phase transition and beyond. We attempt to understand
why phase transitions so often yield hard instances. We believe, and the
evidence supports, that the reason for the exponential growth is the disappearance
of small k 1-critical subgraphs at the threshold. There is no known way
of e-ciently noticing and verifying the existence of large critical subgraphs of
non-k-colorable graphs.
1.1 Overview of the paper
In Section 2.1 we present the model, which we call the full frozen develop-
ment, used to study the properties of the phase transition. Naive methods for
studying frozen development would be prohibitively costly, but in Section 2.2
we present a detailed overview of the techniques we use to calculate frozen
development. In theory these allow the computation to be performed using
O(n 2 log(n)) calls to a graph coloring program, and in practice they allow us
to do the complete computation for n up to 225,
In Section 3 we present the empirical results of the study on our frozen development
model, showing strong evidence that indeed our backbone measures
show a discontinuous jump at the threshold. In particular we show evidence
that a xed fraction of pairs become frozen under the addition of O(1) edges.
We show in Section 3.2 that this jump can be seen as a sudden collapse in the
size of the graph. If we consider the graph induced by the equivalence relation
dened by frozen pairs, the addition of a single edge typically reduces the size
of the graph by 28%. As a nal application of frozen development, we report
in Section 3.3 on new estimates on the probability of colorability into regions
where this probability can be as low as 10 300 .
In Section 4 we present empirical evidence, using two distinct complete al-
gorithms, to show that indeed there is exponential growth in di-culty near
the threshold as n increases. This evidence is a mixture of results measuring
di-culty exactly at the threshold graph from the frozen development process,
and of further graphs generated from the G np model for larger values of n.
In Section 5 we present theoretical and empirical evidence that the smallest
4-critical subgraphs of a non-3-colorable graph are large near the threshold
asymptotically. We correlate this with the hardness of instances empirically
observed. We wonder whether a discontinuity in a backbone is suggestive of
such large critical structures in general.
In the conclusions (Section 6) we discuss the possibility that the discontinuity
exhibited by our measure may not correspond to a discontinuous order parameter
as measured by a minimization of violated edges over all partially correct
3-colorings. If this should prove to be the case, it could have implications for
renements needed in the analysis as applied to this problem.
Frozen Development and Algorithmics
2.1 Full Frozen Development
For purposes of this study, we consider a model based on the set of
un-
ordered pairs of distinct vertices
at random one of the
permutations of the set of pairs, calling this
the input sequence . We build a graph of m edges by choosing the rst m
pairs from the input sequence. For a given sequence  we can determine the
smallest value t() (or t when  is understood) such that the graph on the rst
t() edges is not k-colorable: we call t() the threshold index of the sequence
. We dene the average threshold T (n) as the average over the set of all input
sequences  of the minimum values t.
Using this model gives several advantages in studying the phase transition,
including an expected reduction in variance on computing T (n) for a given
sample size. One of the conjectures on the coloring phase transition says that
for each k, T (n)=n converges to a constant  k as n !1.
In practice we do not want to stop measurement at the threshold index; after
all if some other edge had occurred at this point in the sequence we might be
able to keep on going. In the full frozen development method when a pair m
is added as an edge that renders the graph non-k-colorable, then the edge is
deleted and we move on to the next edge. This gives us a way to smoothly
extend frozen measures beyond the threshold until all pairs have been consid-
ered. At that point, the graph is a maximal k-colorable graph.
To make this more precise we rst present a few denitions.
Given a k-colorable graph G, we say that a pair fu; vg is frozen i for every
coloring c of G, c[v]. The name frozen means that this edge cannot be
in any k-colorable graph containing G as a subgraph.
The spine (or backbone) 2 of a colorable graph G is
We dene the sequence of graphs G
, inductively.
We follow Bollobas et al [2] by dening the scapegoats of this sequence as those
pairs  i which are not included because they occur in the spine of an earlier
graph. The name arises because each scapegoat could be held responsible for
uncolorability if it were added to the graph. That is, the set of scapegoats for
a sequence  is
Note that the rst scapegoat encountered is the threshold for the sequence.
For m < t the graph Gm is the graph formed by the rst m pairs of the
sequence. Notice that G ( n) is a k-partite complete graph.
For each Gm we record all those pairs which are frozen by m. That is, each
remaining pair  is tested and recorded as frozen with crystallization
by Gm and not by Gm 1 . Notice that the
threshold index t is exactly the smallest index m such that m is frozen for
some index ( m ) < m. Also, we see that B(Gm
mg.
We can also compute the smallest value m f of m such that there is some
pair (u; v) of vertices (necessarily with index in the sequence greater than m f )
frozen the same. There may be more than one pair which are forced to be the
same color by the addition of the m f th edge. We call m f the rst edge causing
a frozen pair, or the rst frozen for short. We dene
Clearly, for every sequence , m f ()  t(). Thus,
suming it exists) must be bounded above by . Elsewhere we have presented
evidence to strongly suggest that as n !1,
We choose the term spine because in the full frozen development it most closely
approximates the spine dened in [2]. While not identical, it shares the important
property of monotonicity with the earlier denition.
Analogously to frozen pairs, we can measure for each m the number of pairs
such that for all colorings of Gm , c[u] 6= c[v]. Such a
pair is said to be free. We observe that free is not quite the complement of
frozen. When a pair is frozen it cannot appear in a k-colorable graph which
is a super graph of the current one. When a pair is free its addition makes no
dierence to the set of legal colorings of any super-graph. Thus, in calculating
frozen development we can skip adding these edges, because they simply do
not matter to the set of colorings. 3 As for frozen pairs, the free pairs are
also part of the crystallization process. We associate with each free pair the
crystallization index when it rst became free.
Our program for the full frozen development process on a sequence  produces
as output the type of each pair
. This type is either frozen,
Eective means that for all i < m, m is neither frozen nor free
in G i . Thus the edge is eective in the sense that it is added to the sequence
of graphs without causing uncolorability, and it does reduce the number of
colorings of Gm to less than those of Gm 1 . 4
For each non-eective pair, we record the index at which it rst becomes
frozen or free with the index of eective pairs being set to themselves. With
this information, it is easy to compute the growth of the spine, and of the free
set, as well as other statistics such as the location of the rst frozen and the
threshold.
2.2 E-cient Computation of Full Frozen Development
We turn our attention to the outline of the method we use to compute the full
frozen development. The reader not interested in these details but only in the
empirical results can safely skip to the next section.
Our approach can be broadly classed as a forward scanning method since for
each Gm we create, we scan forward over remaining pairs to determine whether
each is free, frozen or as yet not crystallized. We outline several optimizations
that make this task amenable up to As a result, empirical indications
are that this runs in about O(n 2 log n) calls to our underlying coloring
algorithm. At the end of this section we show that the full frozen development
can indeed be performed in at most O(n 2 log n) calls.
3 When we test the hardness of coloring, all free edges must be added. The free
edges could make a big dierence to a coloring algorithm, for example by preventing
errors high in the search tree.
4 Note that our denitions ensure that eective edges are not free, even though
(trivially) c[u] 6= c[v] in Gm if vg.
To determine whether a pair  is frozen at index m, we test if the
not, the pair is frozen.
To test whether the pair  is free, we merge u to v. A merge requires
v to be deleted and then for every edge fv; zg that was in Gm , we add an edge
fu; zg to Gm - (uv) if it is not already present. If Gm - (uv) is not k-colorable
then the pair fu; vg is free.
These two tests are helpful because they replace an examination of all colorings
to single calls to a graph coloring program. This coloring program can be one
independently developed and highly optimized, and is freed from the space
demand of storing all colorings.
The rst step in our process is nding the threshold of the sequence. For
some purposes, for example when n is much greater than 225, this is the only
step we perform. To nd the threshold index t, we do a binary search to
nd the smallest i such that the graph with the edge set is
not k-colorable and set This requires O(log n) calls to the coloring
program.
To compute the full frozen development using a naive implementation, we
would call a coloring program for each
and for each pair
fu; vg later in the sequence . This would result in
stead, we have taken advantage of the monotonicity of graph colorings to
greatly reduce this number. The rst family of properties we use to reduce
calls are straightforward:
(respectively frozen) at index m =) fu; vg not frozen (not free)
at index m.
uncolorable so we
can skip m .
the set of edges free (frozen) at index
the set of edges free (frozen) at index m 1. Again we can skip m .
We can make further improvements by making use of the coloring found by our
coloring program when the graph given to it is colorable. In particular, we can
greatly reduce the number of calls to the coloring program while calculating
the frozen pairs at a particular index m. We do this by making use of every
coloring found, whether when adding edges or merging nodes. We have the
following facts:
m.
c[u] 6= c[v] =) fu; vg not frozen at index m.
any coloring c 0 for Gm + fu; vg is also a coloring of Gm .
any coloring c 0 for Gm -(uv) can be extended to a coloring for Gm by setting
These facts are more useful than they might appear. When we need to test Gm ,
i.e. we are not skipping pair m , we test the rst pair  whose
status is not known from smaller indices. If Gm+fu; vg is uncolorable, we have
determined that the pair is frozen. If however it is colorable, we can use the
coloring c 1 and the rst two facts above to rule out one of the possibilities for
each If the merge Gm - (uv) gives another colorable graph (in which
case m is known to be eective) we use the new coloring c 2 . For any future
pair fz; wg such that c 1 [z] 6= c 1 [w] but c 2 vice versa, fz; wg is
eective since it can be neither free nor frozen at index m, meaning that we
need not use our coloring program to test either Gm
Typically we will nd many such pairs, greatly reducing the number of calls.
The preceding paragraph gives the information we can glean from the rst pair
at index m. The minimum information we have
about each future pair is that only one possibility of free or frozen remains.
This cuts the number of calls by at least half. As we test each unresolved pair
fz; wg for frozenness, the result will give us signicant amounts of information.
If the pair is frozen, the pair is frozen for all indices i > m. If the pair is not
frozen, we obtain a new coloring. If we are testing fz; wg for being frozen,
all previous colorings must have but the new coloring must have
the case for free is similar. In either case, the new coloring must
be dierent from all previous colorings found for Gm . Barring rare cases, this
will determine some future pairs as being neither free nor frozen.
These optimizations give a dramatic reduction in the number of coloring calls
necessary. In fact, almost every coloring attempt gives us signicant amounts
of information: either that a certain pair is free or frozen for many indices, or
that many pairs are neither free nor frozen at a certain index. We have still
further advantages from the well known easy-hard-easy pattern of coloring,
with hard instances concentrated at the threshold. While we do have to perform
many coloring calls near the threshold, a large number of calls are either
signicantly before or after the threshold: these calls are usually cheap.
Finding the threshold as the rst step also gives another advantage. Typically
the threshold occurs just after a large jump in the number of frozen pairs, as
we will see in the next section. A coloring is an equivalence relation, and so
is frozen. If fu; vg and fv; wg are frozen, then taking the transitive closure
shows that fu; wg is also a frozen pair, and this without a call to the coloring
program. On the rst forward scan from the threshold we typically nd many
frozen pairs, and so many pairs never need be checked. The sharper the rise
in the frozen pairs, the more eective this is.
The net result is that we can test full frozen development in 3-coloring up to
graphs with 225 nodes.
Despite major advantages, our approach may not be optimal. Instead of doing
the forward scan, we can use a backward scanning approach. After using a
binary search to nd t() we know that all pairs are eective or
free, and so require no further testing for frozen. Inductively, after we have
determined the values for the sequence up to m 1, we test Gm 1 +m . If this
is not colorable, then m is frozen. We may then do a binary search on the set
of graphs G adding m to each in turn, to determine ( m ). On the
other hand, if Gm is not frozen, we can merge the pair of vertices in m to see
if it is free. If so, we can do a binary search on the graphs G
the merge on m applied to each in turn, to determine
Otherwise the edge is eective, and requires no further action. This method
will do at most O(n 2 log n) calls to the coloring algorithm. As with the forward
scanning method, many of the potential calls can be eliminated by keeping
track of certain colorings, and taking transitive closures. We leave practical
investigation of that technique for future work. The forward scanning method
is more eective for computing certain partial frozen development information.
3 Empirical Evidence for an Asymptotic Discontinuity
We now report empirical results of full frozen development on 3-coloring, using
the algorithmic techniques developed above. We will show dramatic evidence
strongly suggestive of an asymptotic discontinuity in behavior. Further re-search
is necessary to conrm whether this discontinuity will be apparent in
the order parameter for graph coloring.
3.1 Sudden Freezing in 3-coloring
Our rst empirical observation is that the freezing process is not gradual.
Instead, we see that a large number of pairs freeze at the same index. That is,
the addition of one edge can cause many pairs to become frozen simultaneously.
Typically, just before the threshold, there is a sequence of from 1 to 5 edges
which cause on average 16% or more of the pairs to be frozen. This behavior is
typical of the big jump we might expect if there is an asymptotic discontinuity
in behavior.
In gure 1 we show how the number of frozen and free pairs grows as the
edge density increases. We ran the full frozen development on 100 random
permutations at each value of in steps of 25. This is clearly
Frozen
(n
choose
Edges/n
Frozen Pairs751251752250.10.30.50.7
Free
(n
choose
Edges/n
Free Pairs75125175225
Fig. 1. The ratio of frozen pairs and free pairs to n
plotted against the ratio m=n.
typical of a phase transition, and the sharpness suggests that there will be a
discontinuity at 1. The range over which these curves are plotted is the
entire range over which any dierence in the number of frozen or free pairs
occurred. For the larger values of n it is of course a tiny fraction of the set of
pairs.
In table 1 we present data on the size of the spine at the threshold, and as
one might expect the threshold typically occurs after the big jump, although
occasionally it occurs by sheer accident after only one or two pairs are frozen.
The spine is monotonic, like the spine of Borgs et al [2]. That is, once a
pair is in the spine it remains there as new edges are added. This is dierent
from the backbone of Monasson et al [19], dened with respect to optimizing
assignments. The closest analogy in coloring would be a measure with respect
to all colorings minimizing the number of violated edges. A frozen pair in a
Frozen Pairs at the Threshold
Min Max
100 703.41 335.94 0.14 26 1339
200 3010.74 1283.94 0.15 19 5255

Table
The number of frozen pairs at the threshold. Notice that the number is on average
about 14% of the total pairs, which can be compared to gure 1
colorable graph might become unfrozen after the threshold where no coloring
satises all edges, if some optimal colorings violate the edge and others don't.
We prefer the monotonic measure we use, not least because it makes possible
the O(n 2 log(n)) procedure reported in Section 2.2, but it is possible that
less dramatic behavior would be observed with a backbone-like measure. We
discuss this issue further in the conclusions.
3.2 Collapse in Graph Structure
We have already noted that frozen denes an equivalence relation on G. We
write F for this relation, so that u F v i the pair fu; vg is frozen in G.
This gives us the natural concept of the graph induced by the equivalence
relation, which we denote G=F and call the collapsed graph. If
is the
equivalence class of u. By denition, for every pair of vertices in the collapsed
graph not joined by an edge there is a k-coloring of the graph that makes
the vertices dierent colors. That is, there are no frozen pairs in the collapsed
graph. There may, however, be free pairs of vertices.
The collapsed graph gives us an alternative view of freezing. It addresses
a potential objection, that the big jump in freezing may occur only due to
transitivity. That is, a large number of frozen pairs may occur only because
two equivalence classes merge. We will show that the collapsed graph shows
dramatic behavior, as did the raw number of frozen pairs. This cannot be solely
because of large equivalence classes merging, since that would only entail a
reduction of one in the size of the collapsed graph.
Vertices
Remaining
Sequence Index
Fig. 2. Collapse in fteen 200 vertex instances. The y-axis represents the number of
vertices remaining in the collapsed graph. The x-labels indicate that the x-axis is
the sequence index, that is the number of edges that would be added if none were
skipped.
We can analyze the nature of the collapsed graphs using the same frozen
developments reported in gure 1. We report the sequence of the number of
vertices in the collapsed graph for 3-coloring examples. That is, we report the
number of vertices in Gm =F for each m. Notice that we do not add edges to
the collapsed graph: we calculate the frozen development as before and then
the size of the collapsed graph. In gure 2 we show the collapse in a sample
of fteen 200-vertex graphs, graphs 1-15 of our sample of 100. In each case
there is indeed a sudden collapse near the threshold in each sequence. Each of
these instances drops rapidly somewhere in the range 430 to 470, which when
divided by 200 gives a ratio of 2.15 to 2.35 as we might expect. The threshold
graph typically occurs very shortly after the big drop given that there are so
many frozen pairs lying around after the big drop (the threshold pair must be
a frozen pair). The marked points on the curves represent the eective edges,
that is those edges that were neither frozen nor free in the sequence when
encountered and so were actually added to the graph. The number of eective
edges actually required to cause the catastrophic drop is even smaller than
the range of sequence indices indicates.
If we compute the average number of vertices in the collapsed graph over
the sample set, we no longer see a sudden drop. In this respect, the average
is not a good indicator of what is happening in the individual instances. To
show this, in gure 3 we plot the average number of vertices remaining in the
collapsed graph for each index, together with another set of twenty 200-vertex
graphs. The average is taken over all 100 samples, and the individual graphs
are 41-60 from our sample. Almost all instances exhibit a very narrow range
over which they drop from a fairly well dened region at the top to another at
the bottom. And all have at least one large drop caused by a single edge. The
average really only re
ects the percentage of instances that have dropped so
far, not how fast they drop.2060100140180400 420 440 460 480 500
Vertices
Remaining
Sequence Index
"avg.200"
Fig. 3. A set of twenty sample collapses with with the average of the
entire 100 samples overlaid. Notice that the average does not closely approximate
the shape of any of the curves, even the most atypical case at the far left.
We can use alternative measures to see how fast the size of collapsed graphs
drop on individual permutations. To do so we nd, for each permutation's
full frozen development, the one edge that caused the maximum drop in the
number of vertices on that sequence. Call this the maxdrop of the experiment.
We can now study each permutation's behavior relative to its own maxdrop.
We show this in gure 4. As before the y-axis is the average size of collapsed
graph, but the x-axis is now the number of edges in the sequence before or
after the maxdrop, with the maxdrop edge index represented by
see from gure 4 that the mean maxdrop is from 72% to 44%, a drop of 28%
of the vertices on a single edge. This is represented by a near-vertical jump in
the average curve.
The behavior of the maxdrop is remarkably consistent as we change n. In
gure 5 we plot in the form of error bars for each n the mean, minimum,
and maximum maxdrop of the set of samples. The average of  28% is very
consistent. Even the minimum is consistent, with the smallest fraction at 10%
That is, in every one of the 800 trials, there was a single edge that
caused a fractional drop of at least 10% in the size of the collapsed graph. We
also show, in gure 7 the average location of the maxdrop edge. As expected
the average index of the maxdrop edge appears to be converging towards 2.3.
Another way of measuring the graph collapse is to compute intervals over
which certain drops in the size of collapsed graphs occur. In gure 6 we plot
Vertices
Remaining
Centered on Maxdrop / n
Average of 100 Trials
Fig. 4. The rst ten experiments from gure 2 and the average of all 100 experiments,
but with the samples and average aligned at the index of the maxdrop edge.0.20.61
Maximum
Edge
Number of Vertices
Fig. 5. The average maximum drop on a single edge. The error bars represent the
minimum maximum drop and the maximum maximum drop over 100 samples.
the index (as a ratio to n) where the collapsed graph rst has fewer than 80%
of its original vertices. In contrast, in gure 7 we plot the actual (top) and
relative number of edges required to cause the graph to drop from 0:9n down
to 0:4n vertices. This 50% interval seems not only to be converging relative
to n but even in absolute terms. In fact, there are specic instances where an
edge caused the drop from above 90% to below 40%, causing the measured
number of edges to be zero.
We nd it intuitively surprising that a single edge would cause a xed fraction
of vertices to collapse. However, our empirical evidence strongly suggests that
this occurs in almost every instance. Accordingly we conjecture that it will be
true in the limit. Further theoretical research is necessary to conrm or refute
Maximum
Drop/n
Number of Vertices
of
80%
Mark
Number of Vertices
Rank 100
Rank 90
Rank 11
Fig. 6. (Top) The average index of the maximum drop edge. The error bars indicate
minimum and maximum index over the entire set. (Bottom) The index (as a ratio
to n) where the collapse rst has fewer than 80% of its original vertices. The top
and bottom lines correspond to the full range over the 100 samples while the center
lines bound the 80% of the samples in the middle, a simple minded attempt to
remove the high variance extremes. Note the convergence apparent here, and also
note that in no instance did the rst drop below 80% exceed 2:35n edges.
this conjecture.
Our conjecture is highly suggestive of an asymptotic discontinuity in an order
parameter, as previously seen in SAT. However, on this point we must be less
denite, because it is not yet known what the order parameter for coloring is.
Further, as we have seen, some measures of graph collapse (such as the mean
size of graphs) do not seem to have a discontinuity. The empirical evidence
of sudden collapse in graph is certainly worthy of further investigation from a
statistical mechanics viewpoint.
Average
edges
in
gap
Number of Vertices n
90-40 gap0.20.61
Fraction
Remaining
Before
Edge
Number of Vertices
Fig. 7. (Top) The average over 100 samples of the number of edges in the gap
between the rst drop below 90% and the rst drop below 40%. While noisy, the
actual number of edges seems to be decreasing with n. For example, for 100 vertex
graphs the addition of about 11 edges reduce the collapsed graph from 90 vertices to
40, while only 8 are necessary for to reduce collapsed graphs from 180 to 80
vertices. (Bottom) The minimum, average and maximum of the number of vertices
in the graph at the top of the maximum drop. The average here too seems fairly
consistent with the 72% observed before for that the drop on one
edge is almost equal to the total drop up to that point on average; i.e. 100-72=28.
However, the range can extend anywhere from under 40% to 100%.
3.3 New Estimates of Probability of Colorability
As well as investigating the region where threshold graphs occur, we show
that frozen development is also useful for gaining a more accurate picture of
the phase transition in colorability. The main advantage is that we can get
unbiased estimates of the probability in colorability both where the probability
is very close to one and where it is very close to zero. Additionally we see a
variance reduction compared to simple generate and test, but this reduction
does not repay the computational expense of the method.
Recall that in frozen development we have a permutation  of all
pairs
of vertices. Also, recall that an edge  i is a scapegoat exactly if the edge  i
is not in G i (). The rst scapegoat occurs at the threshold, and thereafter
we see more scapegoats. Any sequence  can be reduced to a scapegoat-free
subsequence dened simply as the set of non-scapegoats in
in the same order in which they occur in . Thus, R() denes the edges in
the k-partite complete graph G ( n) ().
For example, in 3-coloring, the sequence of edges 1-2,1-3,1-4,2-3,2-4,3-4,4-5,5-
reduces to omitted as it completes
a 4-clique. Many dierent sequences reduce to the same scapegoat-free
subsequence. In this example, the sequence
reduces to the same subsequence.
We can use the frozen development to calculate exactly the probability of colorability
over all sequences  0 with the same scapegoat free subsequences as
Note that in this case We use the observation
that this probability is also an unbiased estimator of the probability
of colorability. 5 We explain these steps in detail before presenting empirical
results.
Given a sequence  and its scapegoat-free subsequence R(), there is a family
R() of sequences dened by R()g. Given some index i,
we can ask for a given  0 2 R() whether or not the threshold index, t( 0 ), is
greater than i or not; that is, if the rst i edges in  0 form a colorable graph.
They will do so if and only if the rst scapegoat in  0 occurs at index i
more. Given i, it is natural to ask what is the probability of colorability over
R(), i.e. the value of Prft( 0 assuming that each sequence
equally likely.
Our calculation of the entire frozen development of a sequence  allows us to
exactly calculate the probability R()g. We do so
by induction, using the following equations.
5 We thank David Wilson for pointing this out to us.
The last step follows because the condition implies that none of
the rst i 1 edges in  0 can be scapegoats. This also implies that the rst
edges in  0 are also the rst i 1 elements in the scapegoat-free subsequence
R(). The probability required in the nal line can be calculated very simply
if we have performed a full frozen development. The possible scapegoats are
exactly the pairs frozen in the frozen development of  up to and including the
index in  corresponding to the i 1 th element of R(). Writing P C
;i for the
conditional probability Prf 0
have
In words, the denition of F (i) is the number of frozen pairs in  up to the
location in  where the i th element of R() appears. Note that the value of
F (i) is the same for all sequences  2 R().
We implemented a Perl script to calculate these numbers, given the frozen
development over a permutation of pairs. To illustrate the nature of typical
behavior, we show results in gure 8 of a single instance with
rst calculated the conditional probability P C
;i We see a big jump in the conditional
probability. This corresponds to the sudden jump in the number of
frozen pairs. The probability of a random pair of nodes being consistent with
any coloring is 2. The conditional probability falls below this value because
we are dealing with permutations of pairs, or in other words sampling without
replacement from the set of edges. We were then able to calculate the unconditional
probability of colorability P;i for sequences with the same reduced
subsequence as , and this is shown in gure 8. Immediately after the conditional
probability goes signicantly away from 1, the absolute probability
inevitably collapses. After that it decays exponentially, as can be seen in the
log plot. This plot shows the advantage of our method: these probabilities are
the exact probability of sequences with the same scapegoat-free subsequence
being colorable with this number of edges. No such estimate was previously
possible when the probability declined below about 10 9 , since samples of a
billion would have been necessary, and even this would give only estimates
instead of exact probabilities.
For random instances, the probability P;i is of little direct interest, although
it provides us with a valuable tool for studying non-random problems in the
future. For random instances, the subject of this paper, the probability we are
interested in is the global probability colorableg. Fortunately,
the probability P;i is an unbiased estimator of P i . That is, E(P;i
Single sequence Conditional Probability n=2251e-3001e-2001e-1001
Single sequence probability of colorability n=225
Fig. 8. (Left) The conditional probability P C
;i for sequences with the same reduced
subsequence as a particular  for plotted against i=n. (Right) The overall
probability of colorability P;i for sequences with the same reduced subsequence as
, plotted on a log scale against i=n.
where the expectation is over all sequences .
To justify the claim of unbiased estimation, rst note that
rst i edges in a random permutation are colorableg
This follows because over all permutations, each distinct graph G with i edges
occurs exactly the same number of times, in particular exactly i!(n i)! times.
We can easily prove that P;i gives an unbiased estimator of this equivalent
statement of P i . The key to the proof is that the families R()form a disjoint
union of all sequences . To formalixe the simple proof, we introduce the
indicator function I ;i , which takes the value 1 if the rst i edges in the
sequence  are colorable, and 0 if not. We also extend the notation P;i to
P R();i in the obvious way.
rst i edges in a random permutation are colorableg
I ;i
P;i
The combined result of this development is that we can introduce a new
methodology for empirical estimation of probability of colorability. Instead
of mere 'generate and test', in which we generate a sample of graphs from G n;i
and test them for colorability, we instead generate random permutations and
calculate the entire frozen development. From this, we can calculate for each
sequence  and index i the value P;i and use this as an estimate of P i . Since
this is an unbiased estimate, we can repeat this procedure for a sample of
permutations and use the average to estimate the probability of colorability.
We can now reuse our data on frozen development to present estimates of probability
of colorability up to with a sample size of 100 permutations
in each case. The results are shown in Figures 9 to 10.
Our experiments suggest that the technique is not very useful as a variance
reduction technique where probability of colorability is signicantly away from
both 1 and 0. Where P i  0:5, the sample standard deviation of our estimates
of P i was about 0.4. We would expect a standard deviation of 0.5 using generate
and test. Using a sample only about 50% bigger, we could obtain the
same accuracy of estimation from generate and test, very much cheaper than
by calculating full frozen development.
The value of our experiments is in giving estimates of probability in the highly
colorable and the highly uncolorable region. This is particularly notable in the
highly uncolorable region. We remind the reader that the estimates given are
unbiased estimates of the true probabilities, even where values are as low as
. For the rst time, we can use empirical data to picture the decay
in probability of colorability. One caveat is necessary. We do have estimates
of probability, but it is likely that these estimates may well have very high
variance. For example, if we estimate P the true value of P i may
be sequences gives an estimate of P
currently have no way of judging how accurate these estimates are. David
Wilson suggested that the estimates might give the right order of magnitude
of the logarithm, as in the example just given [27].0.10.30.50.70.91
e/n vs Mean +/- std error
Fig. 9. A broad view of the phase transition in 3-COL for varying n, plotted according
to the method introduced here. Error bars show +/- one standard error,
i.e. sample standard deviation divided by the square root of sample size. In this
case the sample was of 100 random permutations at each n. This gure shows little
that would not be seen in a more conventional plot, except that the errorbars are
slightly narrower than would be expected.
4 Hardness of Coloring Problems at Thresholds
We have seen a sudden jump in graph behavior. If this does connect with
an asymptotic discontinuity in an order parameter, by analogy with SAT we
should see that 3-colorability shows hard behavior at its threshold. Accord-
ingly, we investigate this question in this section. Our evidence is strongly in
favor of the belief that graph 3-coloring does indeed become hard at its thresh-
old. This is also consistent with previous results from the literature [3,10]. In
this section we present new empirical results to further support this claim.
In gure 11 we plot the growth in the average number of search nodes used to
determine the colorability of the colorable (i.e. graphs with t() 1 edges) and
uncolorable graphs at the threshold (t()). To obtain the threshold graphs for
used our frozen development binary search to locate the threshold
but did not compute the frozen sets. There are 100 instances at each n.
Both the median and average costs clearly exhibit exponential growth.
Notice that for small n the cost of the colorable graph is greater than the cost
of the uncolorable graphs with one more edge. This changes as n gets larger,
2.36 2.38 2.4 2.42 2.44 2.46 2.48 2.5
e/n vs Mean +/- std error
n=1251e-251e-151e-052.2 2.4 2.6 2.8 3 3.2
e/n vs Mean +/- std error
Fig. 10. (Top) A close up of the region where all n give very similar behavior. All
error bars seem to cross at about e=n  2:4. (Bottom)A close up of the highly
insoluble region. Note the logarithmic scale, showing that beyond about
we are obtaining estimates of colorability entirely beyond the reach of conventional
techniques.
with the uncolorable cost being more than twice as great at
reason is that for the smaller values of n there is a high probability that the
threshold graph contains a 4-clique, which is detected during initial pruning
and so the search uses no backtrack nodes. As the analysis in Section 5 shows,
these disappear with increasing n.
To study larger n, to get a picture of the distribution at various densities
and to ensure that the problem is hard for algorithms other than our Smallk
program, a series of experiments were run on graphs from the class G np . In
the rst experiments random graphs were generated with the edge parameter
ranging from 2.29 to 2.31, which is near the conjectured threshold. Recall
Average
Number
of
Search
Nodes
Number of Vertices
Uncolorable
Colorable t-1464102416384
50 100 150 200 250 300 350
Median
Number
of
Search
Nodes
Number of Vertices
Uncolorable
Colorable t-1
Fig. 11. The average (Top) and median (Bottom) number of search nodes used by
Smallk for threshold graphs.
that the expected number of edges is E
. Each graph was then
tested using the Smallk program and the Ntab back program. The Ntab back
is a SAT solver which implements the tableau method[5] with back jumping.
It has been shown to be very e-cient on short clauses, such as those generated
by the conversion we describe next.
There are many ways to represent a coloring instance as a SAT instance.
In preliminary tests we tried several of these and settled on the one in g-
ure 12 (referred to as Version 2.5) as being the one that performed best with
Ntab back.
Version 2.5 considered here and used in the experiments begins to cross the
line from a pure representation to one in which some solution information is
carried in the representation. On considering the results for
the symmetry breaking, it became evident that one of the di-culties faced by
Variables to the set of variables
U. The meaning is that if v i is true then vertex v gets
color i.
Color Vertex to the set of
clauses C. The meaning is that if the clause is true
then at least one of the colors is assigned to the vertex.
Edge Check 8 fu; vg 2 E, for each
to C. The meaning is that the same color
cannot be assigned to both end points of an edge.
Only One Color 8v 2 V; 81  i < j  k add h
to C. This means at most one of the colors can be
assigned to v.
Symmetry Breaking For exactly one edge
add the two clauses hu 1 i and hv 2 i to C.
Variables: nk
Clauses: 2 1-clauses; mk
Fig. 12. Version 2.5 used to represent a k-coloring instance ki as an
instance (U; C) of SAT. Here
the SAT search engine especially on unsolvable instances, was that it had no
way of preventing searches that basically relabeled the color classes.
In Version 2.5 symmetry breaking information is presented to SAT. Basically
an edge is detected in G and the two vertices are forced to distinct colors 1
and 2. This is a trivial addition to a conversion program since edges must be
checked anyway. However, it does open a can of worms if our goal is to check
the relative e-ciency of two approaches. If we are allowed to add arbitrarily to
the converter, then with su-cient eort we could simply encode the solution,
which the SAT program would merely have to output. Of course we could add
the time for conversion to the time for the SAT routine, but this opens up
other questions of e-ciency of the conversion.
Similarly, the \Only One Color" clauses are not strictly necessary. But again
preliminary tests indicated these 2-clauses occasionally helped on the harder
instances for small values of k, and seldom caused Ntab back to require more
time. A number of other conversions were also tested, but none were competitive
with this for
Using this conversion on the instances of 3-coloring considered here, usually
the two programs were within a factor of 8 or less in run time, with both
\winning" equally often. Conversion times were not considered, being only a
tiny fraction of the search time. Rarely, one or the other program would take
considerably longer than the other, up to a factor of 50 or more. This typically
occurred on instances that were solvable, where one program would get lucky
and solve the instance very quickly. For k > 4, Smallk was almost invariably
faster, frequently by orders of magnitude.
For this section the minimum time from the two programs was extracted. 6
This minimum time is used in as the indicator for the growth rate of the solving
cost. 7 In gure 13, we present evidence that the cost is growing exponentially,
even at the 25% rank.416642561024
Min
Time
Number of Vertices
50% All 100 Instances2.300.25141664400 450 500 550
Min
Time
Number of Vertices
25% All 100 Instances2.30Fig. 13. The growth rate in the cost of coloring or proving uncolorable. There are
100 instances at each of 400, 450 and 500, but only 25 instances at 550. Three edge
densities are reported, from 2.29 to 2.31. (Top) The 50% rank. (Bottom) The 25%
rank.
6 In two cases Ntab back incorrectly asserted that there was no solution. In these
instances the time from Smallk was used, but in others we continue to use the
Ntab back time on the assumption that a debugged Ntab back would probably give
similar results to the version we used.
7 For an accurate estimate of resource usage, this time should be multiplied by 2.
There is a large dierence between the typical cost of solvable and unsolvable
instances. In gure 14 the instances are split into those that were colorable
and those that were not. For n  500 a time limit of one hour was placed
on each program. This time limit was exceeded by both programs in three
instances: one instance at 2:30, and two instances at
2:31. These are included as unsatisable instances in gure
14. For was removed, but there are only 25 instances
at each data point. Both satisable and unsatisable instances appear to be
increasing in di-culty at an exponential rate, with an almost constant ratio
in median times between the two cases.1162564096
Min
Time
Number of Vertices
50% Split SAT and Rest
2.29 Rest
Rest
2.31 Rest
2.29 SAT
2.31 SAT
Fig. 14. Splitting the instances into those that are satisable and those that were
not at the 50% rank indicates that both are growing exponentially, although the
satisable instances are more than an order of magnitude easier. \Rest" indicates
that in three cases both programs exceeded the one hour time limit, but were
assumed to be unsatisable.
To obtain a better picture of where the hard instances are, sampling was done
ranging from 2:64. The prole for three
ranks is plotted in gure 15. We also indicate the number of unsatisable
instances at each sample point, demonstrating that the plotted region encompasses
the entire transition from colorable to uncolorable for these instances.
These gures support the contention that there is a broad band of hard instances
at In fact, the frequent hard instances occur well beyond the
2.31 threshold where 50% of the instances become unsolvable to
beyond.
As further evidence a series of tests were run at 700. Extrapolating from
gure 13 we would expect the median cost at 2:31 to be in the region 10-
hours for these sample points, making extensive unbounded tests infeasible.
2.15 2.2 2.25 2.3 2.35 2.4 2.45 2.5 2.55 2.6 2.65
Min
Time
Edges /n
Profile at n=500
75%
50%
2.15 2.2 2.25 2.3 2.35 2.4 2.45 2.5 2.55 2.6 2.65
Number
of
Instances
Edges /n
UnFin
UNSAT
Fig. 15. (Top) The cost of the 25%, 50% and 75% ranks at
were taken at every 0:01. There are 100 instances at
each sample point. (Bottom) The number of instances that were not satisable. The
little tops indicate the number of instances on which both Smallk and Ntab back
exceeded the one hour time limit. It is likely that most of these were unsatisable
as well.
Instead, we opted for a time limit of one hour, using only the Smallk program. 8
The results show that indeed the median cost is greater than 1 hour in many
cases. Given that the median cost at does not exceed 121 seconds
for any , growth to a median in excess of 3600 seconds at re
ects
a growth rate of at least n 10 over this range, su-cient to convince us that
the instances are typically hard. We thus believe that the presentation in
gure 16 is a reasonable representation of the di-culty region at
8 For the harder instances it is rare for the two programs to be out by more than a
factor of 4 to 8, so we do not expect signicantly dierent results if Ntab back were
also used.
This evidence is consistent with the conjecture that the hard region is in fact
growing in width (as a ratio to n) as n increases, with 50% or more of the
instances being hard from  less than 2.3 to 2.5 or more.51525
2.15 2.2 2.25 2.3 2.35 2.4 2.45 2.5 2.55 2.6 2.65
Number
Timed
Out
Edges /n
Profile N=700
Fig. 16. The number of instances that were not completed in one hour,
instances at each sample.
5 Critical Graphs and Thresholds
The most fundamental question that must be addressed in understanding
the link between the nature of the order parameter and the di-culty algorithms
have in solving instances is the nature of the constructs that cause
the algorithms di-culty. For graph coloring, almost all search algorithms proceed
by restricting the set of colorings in some way, either by assigning colors
to selected vertices, or by restricting the available colors for vertices, or by
modifying the graph in some way that re
ects a restricted set of colorings
such as merging two independent vertices or adding an edge. Some algorithms
use a combination of these techniques.
When a graph is uncolorable, all such methods must eventually fail. If a graph
is colorable, then the increasing restrictions can create a situation in which
there is no solution. In either case, the graph (with possibly some coloring
restrictions) will contain a subgraph which is su-cient to show uncolorability.
The e-ciency of these algorithms depends on nding and verifying (at least
implicitly) at least one such uncolorable substructure.
A graph E) is k 1-edge-critical if it is not k-colorable, but every
subgraph on a proper subset E 0  E is k-colorable. We use the term critical to
mean edge-critical. Clearly, such a G is k+1-colorable. It is apparent from the
preceding paragraphs that the size, number and structure of critical subgraphs
of an uncolorable graph are of paramount importance to the e-ciency of
most search algorithms. Studying critical substructures can help us understand
hard instances [12,7,1]. We observe that an instance cannot be hard if it is
unsolvable for reasons detected by an algorithm in polynomial time: in the case
of coloring this occurs when instances contain a small critical subgraph. For
example, non 3-colorable graphs are easy to detect if they contain a 4-clique.
It is well known (see e.g. Palmer [20] chapter 3) that the threshold probability
for 4-cliques for graphs drawn from the G n;p class is 1=n 2=3 . This means O(n 4=3 )
is an upper boundary on the number of edges in random graphs that may be
hard, since programs such as Smallk easily detect 4-cliques.
In the appendix we show that 4-critical subgraphs are of
order
Note that this probability corresponds
to an expected number of edges
Although this result suggests the likelihood that the hard region extends well
beyond the threshold asymptotically, the n 4=3 boundary has little to do with
the actual range of hard instances encountered in our empirical study. If we
want the smallest critical subgraphs to be of order z, that is n "  z, and we
choose then we would require n  z 250 according to this formula.
Thus, even to get a high probability that the minimum critical subgraph is of
order greater than 4 (i.e. to avoid 4-cliques) would require n > 2 500 .
Using techniques similar to those in [4] it can be shown that for
smallest critical subgraph will be
n) with high probability. Indeed for
1=n 11=12  the smallest resolution proof (under the straightforward reduction
to SAT) will be super polynomial [14].
Although large critical subgraphs are necessary for hard non-colorable in-
stances, being large is not su-cient. Starting with 4-cliques, arbitrarily large
4-critical graphs can be constructed using only the Hajos join construction
[8] 9 which, even when embedded as subgraphs in larger graphs, could be recognized
immediately using techniques similar to those in Smallk as not having
a 3-coloring. The reason is that in these graphs there are always at least two
near-4-cliques (n4c's; 4-cliques with one edge removed). In n4c's the two independent
vertices are frozen, that is they must be the same color. These lead
to chains of collapse that show immediately that the graph is not 3-colorable.
Thus, the structure of the critical graphs must be such that they are not easily
recognized. It is known that the threshold for n4c's is 1=n 4=5 [20, chapter 3].
Thus, for random graphs with o(n 6=5 ) edges these will disappear asymptot-
9 Given two non-colorable graphs G 1 with edge fx; yg and G 2 with edge fv; wg,
the join construction creates a new graph by deleting the two edges, merging the
two vertices x and v, and adding the edge fy; wg.
ically. By considering the expectation formula, we nd that for
1)(n 2)(n 3)=4) 1=5 the expected number of n4c's is approximately one.
The ratio of the expected number of edges to vertices at
is 2.45, which is a little greater than the threshold for three coloring.
This range compares well to the top of the hump in gure 16. However, hard
instances occur well above even this boundary. Apparently the presence of a
few n4c's is not enough to make the coloring task easy.
What may not be apparent from the analysis is that as we increase the number
of nodes, when the 4-cliques disappear we see a sudden jump in the size of
4-critical graphs to ones
with
n) edges.
Critical Subgraphs of Threshold
Small Cases Remaining Cases

Table
Size distributions of the critical subgraphs of threshold graphs, 3. 100 samples
were taken at each n.
In table 2 we show a breakdown of certain critical subgraphs of the threshold
non-3-colorable graphs. We have separated out very small critical graphs, that
is 4-cliques and other small graphs with up to 12 edges, and other critical
graphs. Two features of table 2 are particularly important. First, we see a
reduction in the number of small critical graphs, from more than 10% of cases
at to only a few percent. At there are three occurrences of
4-cliques, but the next smallest critical graph we observed contains 36 edges.
This data seems consistent with the hypothesis that there will be a sudden
jump in the size of the critical subgraphs. Second, the growth in size of the
larger critical graphs is striking. Indeed, these graphs are growing faster than
linearly with n. That is not possible asymptotically, since the threshold occurs
at O(n). We take this as evidence that critical graph size is O(n), and we
assume that the apparent superlinear growth is towards some xed ratio of
critical graph size to n.
The critical graphs we report above may be unrepresentative. Those we report
are found by randomly permuting the edges of the threshold graph, then deleting
the edges in order, replacing each edge that causes the graph to become
colorable. Thus, they may be may be either unusually large or small, although
there is a straight forward argument that smaller ones will be the most prob-
able. It would be interesting to determine the minimum critical subgraph in
each instance. Unfortunately this will likely prove di-cult, possibly almost as
hard as listing all critical graphs. Further investigation is needed on how to
compute all critical graphs [23].
The critical set of edges in G is the set of edges that occur in every critical sub-graph
of the graph. Thus, these act as a lower bound on the size of the smallest
critical subgraph, although the smallest critical subgraph can be arbitrarily
larger than the critical set of the graph. Note that an edge is in the critical
set i its removal from G makes G uncolorable. This gives a straightforward
way of computing the critical set.
By computing critical sets, we have a lower bound on the size of the smallest
critical graph. All edges in the critical set must be examined by any algorithm
conrming uncolorability. In table 3 we report the number of edges in critical
sets at the threshold, and in gure 17 we show the distribution of sizes of
critical sets for 225. The minimum often obtains its minimum possible
value of 1, since the scapegoat edge is always critical. Despite this, we see
a mean size of critical set of  0:35n. This suggests that the critical set is
growing linearly, as is the critical graph size.
Size of Critical Sets
200

Table
The critical sets, that is the number of edges that must occur in every critical
subgraph of the threshold non-3-colorable graphs. Notice that there is a distinction
between scapegoats and edges in the critical set of the threshold graph. Given the
sequence  used to generate the graph, the scapegoat is uniquely the last edge
added to form the uncolorable threshold graph. This edge must be in the critical
set, because its removal makes the graph colorable. There may be many other edges
in the critical set.
Number of Edges
Histogram of Threshold Sets at n=225
Fig. 17. Distribution of the number of the number of edges in the critical set at
These edges are those in the threshold graph whose removal makes the
graph colorable. There is always at least one such edge, i.e. the scapegoat added as
the last edge in the threshold grpah.
The result that critical graphs are O(n) at the threshold and that they grow
very quickly to this size once the graphs are large enough to prevent 4-cliques
means that more intelligent algorithms cannot be expected to perform significantly
better, unless some remarkable new method for proving uncolorability
with structures other than subgraphs is discovered. Thus phase transition
instances can be expected to be hard for all algorithms. We have reported
experiments elsewhere with 4-coloring and triangle-free random graphs for 3-
coloring [6]. In both cases almost all critical graphs were hard, and there was
very little distance between the rst frozen and threshold points. We conjecture
that similar results will apply to other NP-complete problems in which
phase transitions provide hard instances. It would be especially interesting to
study problems such as the TSP, in which the analogue of critical graphs are
not so obvious.
The fact that there are large (O(n)) critical sets may also have implications
for statistical mechanical analysis. We have dened a threshold with respect
to the frozen development process as the edge which when added causes the
graph to become non-k-colorable. Let us refer to this as the t 0 threshold. The
subscript 0 refers to the fact that we will 3-color the graph with no edge
violations
We suggest that we can take the frozen development measure for a sequence
of thresholds, t We say that a graph is (k; v)-colorable if it can be
k-colored by violating at most v edges.
An edge is violated by a coloring c if both endpoints receive the same color.
We say that a pair of vertices (x; y) is (k; v)-frozen under (k; v)-colorings if
(1) G is (k; v)-colorable,
and
(2) for every (k; v)-coloring c of G we have
Note that if we set then this is exactly the same frozen we have used
previously. Also, if a pair is frozen in Gm , then it is frozen for every (k; v)-
colorable graph Gm 0
in the sequence where m 0 > m.
Now we are ready to dene the multiple thresholds. We dene the (k; v)-
threshold as
In an analogous manner we can also dene (k; v)-scapegoats, the (k; v)-spine
and so on to complete a (k; v) frozen development process. Although in principle
we can now use our frozen development process, the cost of doing so will
be very high.
One indication about (3; 1)-colorings we do have comes from the size of the
(3; 0)-critical sets. Note that on the index before the threshold graph, that is
the last 3-colorable graph at t 0 1, any of the approximately 2:3n edges may
be violated in a (3; 1)-coloring. However, at the next edge every (3; 1)-coloring
must violate exactly one of the edges in the (3; 0)-critical set. The data in Table
3 show that this is approximately 0:35n on average. However, an average of
0:35n nevertheless represents a large increase in the freedom of a (3; 1)-coloring
over a (3; 0)-coloring. Each of the edges in the threshold set gives a distinct
set of 3-colorings of the graph when it is the one edge violated, since that pair
of vertices receive the same color only in those colorings. We expect that at t 0
the set of (3; 1)-frozen pairs will be much less than the number of (3; 0)-frozen
pairs. Each separate violation will result in a dierent set of pairs being frozen
the same. Similarly, at t i the number of (3; i +1)-frozen pairs may be less than
the number of (3; i)-frozen pairs.
When statistical mechanical models are used to study the phase transition
typically the order parameter is based on some measure of coloring similarity
taken with respect to the minimization of violated edges, corresponding to
clauses in SAT [16]. Under our notation, the measure of coloring similarity
would be taken at min v such that G is (3; v)-colorable. We have used the
number of frozen pairs as the measure of coloring similarity, but the above
discussion should apply to any similarity measure.
Thus, we believe it is possible that the sudden jump we see in the similarity
measure for the (3; 0)-spine may not be evident if the measure were instead
taken with respect to minimum violation colorings. This raises the possibility
that the absence of a discontinuity in the order parameter may not necessarily
correlate to easy instances.
We also do not have a solid theoretical link showing that the presence of
a large jump implies that the minimal critical structures are large and lack
properties that make them easily identiable. Although there are interesting
empirical connections, supported by this research, in our opinion neither the
necessity nor su-ciency of rst order transitions for hardness have been shown.
In fact, although large critical graphs and discontinuity at the threshold are
both evident in our empirical and theoretical results, we still have only weak
explanations that link the two phenomena.
6 Conclusions
Our contributions in this paper are in two areas: the frozen development of
graph coloring as we add edges to graphs; and the reasons why graphs found
near the colorability threshold are hard to color.
We have described the notion of 'full frozen development' of graphs. This gives
rise to a denition of the spine of a graph, analogous to the backbone or spine
of a satisability problem. We have shown that the full frozen development can
be calculated in O(n 2 log n) calls to a graph coloring program, and reported
the practical algorithm we use to calculate full development up to
We also showed that this can be used to calculate unbiased estimates of the
probability of colorability in regions even where this probability is
and we reported empirical estimates of probability using this method.
We have reported a number of novel empirical results on the development of
the spine. We showed empirically that the spine of a graph shows a dramatic
jump, usually just before the threshold in colorability. Since this measure is
based on elements (pairs) which are quadratic in the number of vertices, we
also converted this measure to one of counting the number of equivalence
classes forced by the set of three colorings. This results in what we call a
'collapsed' graph, which shows a sharp drop in size corresponding to the jump
in frozen pairs. The collapse is always as dramatic as the freezing. Every
instance we studied showed a collapse of at least 10% in size when a single
edge is added, and the average was 28%.
In terms of the di-culty of coloring, we reported empirical results demonstrating
that there is a widening range over which the best programs available,
including a conversion to SAT, show exponentially (in n) increasing median
time. This median growth rate is  2 n=25 over the range examined. We then
analyzed the nature of critical graphs at thresholds, theoretically and empir-
ically. Unless remarkable new methods are discovered, large critical graphs
correspond to hard instances, because algorithms have to investigate a large
number of edges to prove uncolorability. We observed that at small n, very
small critical graphs such as 4-cliques do occur, but that when these disappear
there is a sudden jump to critical graphs of size O(n). This result agrees
with prior conjectures, and is supported by theoretical results on hardness of
We are aware that the spine we have introduced may not be the order parameter
for 3-COL. Our denition is similar to the spine in SAT dened by Borgs
et al [2], although not exactly analogous. A minimum edge violation coloring
approximation, would be closer to the backbone measure of Monasson et al
[19]. If we used a backbone-like measure, this sharp (discontinuous) change
might be reduced or eliminated. The empirical evidence supporting this is
based on the critical sets, that is the set of edges such that the removal of any
one of them would make the uncolorable graph colorable. At the threshold,
this set is on average large, possibly 0:35n or larger. This means that allowing
one edge to be violated might cause the t 0 threshold to exhibit few or no frozen
pairs. To verify this conjecture we will probably need to make our programs
more e-cient, as the number of colorings needed could be signicant.
We hope that these results will contribute to the analysis using statistical mechanics
of phase transitions in graph coloring. In particular, the occurrence of
a jump in freezing and a collapse in graph size is highly suggestive of a discontinuity
of an the order parameter. In satisability, such a discontinuity has
been correlated with the hardness of 3-SAT instances. Since we have reported
results suggesting both a discontinuity and the hardness of 3-COL instances,
we hope that future investigations will uncover a link like that found in SAT.



--R



Where the really hard problems are.
Many hard examples for resolution.
Experimental results on the crossover point in random 3-SAT
Well out of reach: why hard problems are hard.
The satis
Remarks on the graph colour theorem of Haj
Can't get no satisfaction.
The hardest constraint problems: A double phase transition.
The main properties of random graphs with a large number of vertices and edges.
A new look at the easy-hard-easy pattern of combinatorial search di-culty
Determining the chromatic number of a graph.
Personal communication
Hard and easy distributions of SAT problems.
Statistical mechanics of the random k-sat model
Phase transition and search cost in the 2
Determining computational complexity from characteristic 'phase transitions'.

Graphical Evolution: An introduction to the Theory of Random Graphs.
Clustering at the phase transition.
An empirical study of phase transitions in binary constraint satisfaction problems.
Finding all muses
Locating the phase transition in binary constraint satisfaction problems.

The Gnm phase transition is not hard for the Hamiltonian cycle problem.
Personal communication
personal communication.
--TR
Graphical evolution: an introduction to the theory of random graphs
Many hard examples for resolution
The hardest constraint problems
Experimental results on the crossover point in random 3-SAT
3-coloring in time 0(1.3446^n)

--CTR
Roger Mailler, Comparing two approaches to dynamic, distributed constraint satisfaction, Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, July 25-29, 2005, The Netherlands
Syed Ali , Sven Koenig , Milind Tambe, Preprocessing techniques for accelerating the DCOP algorithm ADOPT, Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, July 25-29, 2005, The Netherlands
Karen Meagher , Brett Stevens, Covering arrays on graphs, Journal of Combinatorial Theory Series B, v.95 n.1, p.134-151, September 2005
Adam Beacham , Joseph Culberson, On the complexity of unfrozen problems, Discrete Applied Mathematics, v.153 n.1, p.3-24, 1 December 2005
Peter Jonsson , Andrei Krokhin, Recognizing frozen variables in constraint satisfaction problems, Theoretical Computer Science, v.329 n.1-3, p.93-113, 13 December 2004
Gabriel Istrate , Stefan Boettcher , Allon G. Percus, Spines of random constraint satisfaction problems: definition and connection with computational complexity, Annals of Mathematics and Artificial Intelligence, v.44 n.4, p.353-372, August    2005
Stefan Boettcher, Evolutionary local-search with extremal optimization, Neural, Parallel & Scientific Computations, v.10 n.2, p.249-258, June 2002
Paul Beame , Joseph Culberson , David Mitchell , Cristopher Moore, The resolution complexity of random graphk-colorability, Discrete Applied Mathematics, v.153 n.1, p.25-47, 1 December 2005
spine;threshold phenomena;frozen development;graph coloring;backbone