Constructing an asymptotic phase transition in random binary constraint satisfaction problems.
The standard models used to generate random binary constraint satisfaction problems are described. At the problem sizes studied experimentally, a phase transition is seen as the constraint tightness is varied. However, Achlioptas et al. showed that if the problem size (number of variables) increases while the remaining parameters are kept constant, asymptotically almost all instances are unsatisfiable. In this paper, an alternative scheme for one of the standard models is proposed in which both the number of values in each variable's domain and the average degree of the constraint graph are increased with problem size. It is shown that with this scheme there is asymptotically a range of values of the constraint tightness in which instances are trivially satis-able with probability at least 0.5 and a range in which instances are almost all unsatisfiable; hence there is a crossover point at some value of the constraint tightness between these two ranges. This scheme is compared to a similar scheme due to Xu and Li.
Introduction
Following the paper by Cheeseman, Kanefsky and Taylor [2] in 1991, phase transition
phenomena in NP-complete problems, including constraint satisfaction problems
(CSPs), have been widely studied. In CSPs, using randomly-generated in-
stances, a phase transition is seen as the tightness of the constraints is varied; when
the constraints are loose, there are many solutions and it is easy to nd one; when
the constraints are tight, it is easy to prove that there are no solutions. Hard instances
occur over the range of values of the constraint tightness corresponding to
an abrupt fall in the probability that an instance has a solution from near 1 to near
0. The peak in average cost of solving an instance occurs, empirically, at or near
the crossover point, where the probability of a solution is 0.5.
A number of possible models for generating random CSPs are discussed in section
2. However, Achlioptas et al. [1] showed that these standard models do not have
a phase transition in the same sense as other NP-complete problems such as graph
colouring, because 'asymptotically, almost all instances generated will not have a
solution'. They proposed an alternative model for generating random instances,
described below. However, in this paper, it is shown that the di-culty is not
necessarily with the way in which the standard models generate instances, but in
the way that the parameters change as the problem size increase, and it is proved
that for one of the standard models, there will asymptotically be a crossover point
when the constraint tightness is within a certain range.
Random Binary CSPs
A constraint satisfaction problem (CSP) consists of a set of variables X= fx
for each variable, a nite set D i of possible values (its domain); and a set of con-
straints, each of which consists of a subset fx of X and a relation R
informally, the constraint species the allowed tuples of values for
the variables it constrains. A solution to a CSP is an assignment of a value from
its domain to every variable such that all the constraints are satised; a constraint
is satised if the tuple of values assigned to the variables it constrains is in the
constraint relation. A k-ary constraint constrains k of the problem variables; in a
binary CSP, all the constraints are binary.
Instances of binary CSPs can easily be generated randomly since a binary CSP
can be represented by a constrant graph and a set of constraint matrices. The
constraint graph of a binary CSP is a graph in which there is a node representing
each variable and for every constraint there is an edge linking the aected variables.
constraint relation between a pair of variables with m 1 and m 2 values in their
respective domains can be represented by an of Boolean values, in
which a 0 indicates that the constraint does not allow the simultaneous assignment
of the corresponding pair of values, and 1 that it does. Each entry of 0 in a constraint
matrix corresponds to a nogood, i.e. a forbidden pair of variable-value assignments.
Random binary CSPs can be generated using a simple model described by the tuple
is the number of variables, m is the uniform domain size, p 1 is
a measure of the density of the constraint graph, and p 2 is a measure of the tightness
of the constraints. We rst generate a constraint graph G, and then for each edge in
this graph, we choose pairs of incompatible values for the associated con
ict matrix.
(Note that each edge will have a dierent constraint matrix associated with it.)
There are several variants of this basic model, diering in how they treat p 1 and
we can either choose exactly p 1 n(n 1)=2 of the available edges or choose each
edge independently with probability p 1 . Similarly, in forming a constraint matrix,
we either choose exactly of the possible pairs of values to be the incompatible
pairs for this constraint, or choose each pair independently with probability p 2 .
If both p 1 and p 2 are treated as probabilities, we get the model termed Model
A in [14]; if both p 1 and p 2 are proportions, we get Model B. Many experimental
and theoretical studies of random binary CSPs have used a model equivalent to
one of these (see [5] or [11] for a survey). Sometimes, p 1 is treated as a proportion
and p 2 as a probability, giving Model D, and for completeness, Model C has p 1 as
a probability and p 2 as a proportion. In Models B and D, the constraint density,
vary continuously, since the number of constraints must be integral,
and the number of constraints might be a better parameter for these models. Some
researchers have indeed used models equivalent to Models B or D, using the number
of constraints as a parameter.
3 Phase Transition Studies in Binary CSPs
Most investigations of phase transitions in binary CSPs have been more concerned
with observing and explaining the behaviour of samples of problems at specic parameter
values than with how behaviour changes with problem size. Some have
been concerned with predicting where the hardness peak will occur (e.g. [14]). Others
consider the rare instances in the under-constrained region whose solution cost
is extremely high (e.g. [10, 6, 15]). It has also become standard practice for CSP
researchers proposing new algorithms or heuristics to show performance comparisons
across the phase transition, both because performance improvements in the
hard region are most worthwhile, and because one algorithm may not be uniformly
better or worse than another across the whole range of constraint tightnesses.
Furthermore, most experimental studies have not considered a wide range of
problem sizes, because of the di-culty of solving large samples of CSPs with many
variables. Typically, random CSPs have been generated with
problem sizes have then rarely been more than 100 variables. Occasionally problems
with e.g. [4], and then larger problem sizes have been
possible. Prosser [13] carried out an extensive investigation of CSPs generated
using Model B. In three series of experiments, he showed the eect of varying one
of the other parameters as well as in one series, the number of variables
varied (from 20 to 60) while m and p 1 were constant.
Grant and Smith [7, 8], in experiments comparing two CSP algorithms, explicitly
considered the eect of increasing problem size, and proposed keeping the average
degree of the constraint graph constant at the same time. Empirically, over the
range of sizes that were considered (20 to 50) this ensures that the peak in average
di-culty occurs at roughly the same value of p 2 for each value of n. There is some
theoretical justication for this. The crossover point is predicted to occur when the
expected number of solutions, E(N) is equal to 1. Since
if m and d are xed as n increases, the value of p 2 for which E(N)=1 will also be
constant. However, this has been shown to be a poor predictor of the crossover point
when the constraint graph is sparse. In [5], it was shown that, if the degree of the
constraint graph rather than the constraint density is kept constant, the di-culties
identied by Achlioptas at al. emerge much more slowly as problem size increases.
Nevertheless, their asymptotic result still holds, so that the crossover point will not
occur at the same value of p 2 indenitely as n increases.
Smith and Dyer [14] considered two ways in which the other parameters of Model
might change as n increases (p 1 constant; m constant or considering
the accuracy of the prediction of the crossover point given by E(N) = 1. They
pointed out that if m is constant the crossover point will eventually be smaller than
the smallest value of p 2 allowed by Model B, for large enough n, so that almost all
instances generated will have no solution. This will also be true if
To summarise, there has been little discussion of how the parameters m and
should increase with n, largely because the focus has been on discussing the
behaviour of CSPs at experimental sizes, rather than on asymptotic behaviour.
There has, however, been an implicit assumption that as problem size increases,
the domain size, m, should remain constant. This is perhaps by analogy with graph
colouring problems. Graph colouring problems can easily be represented as binary
CSPs, with a variable for each node in the graph; the domain is the set of available
colours. 3- and 4-colouring problems were considered in [2]. Clearly, the domain
size for k-colouring problems is k, however large the graph.
Achlioptas et al. [1] showed that these standard models do not have a phase
transition in the same sense as other NP-complete problems such as graph colouring,
because asymptotically, as n !1, almost all instances are unsatisable, provided
that it is a proportion. They show,
in fact, that asymptotically almost all instances are trivially unsatisable, in the
sense that there will be at least one variable which has no value consistent with the
values of adjacent variables. This is shown to be true if the average degree of the
nodes in the constraint graph is constant; if the constraint density is constant, then
the number of constraints grows even faster with n so that trivially unsatisable
instances will occur earlier. In both cases the domain size is assumed to be constant
with n. They attribute the di-culty to the fact that the constraint matrices are
random rather than structured (as for instance in graph colouring) and suggest
that it can be dealt with by changing the way in which the constraint matrices are
generated.
In [1], Model E is proposed as an alternative: rather than generating the constraint
graph and the constraint matrices separately, in Model E, a prescribed number
of nogoods are selected at random. However, a disadvantage of this model is
that as the number of nogoods increases it rapidly generates a complete constraint
graph, most of the constraints having only a small number of forbidden pairs of
values. This makes it unrepresentative of the CSPs that arise in modelling real
problems.
Models A, B, C and D specify only how a set of instances should be generat-
ed, given values of n; m; p 1 and p 2 . They say nothing about how the parameters
should change as n increases. It has been shown that if m and either p 1 or the
average degree of the constraint graph, d, are constant as n increases, there is not
an asymptotic phase transition. However, this does not necessarily require us to use
a dierent set of models. We could instead consider changing m and/or p 1 or d as
increases. Here, a scheme for using Model D and changing the other parameters
with n is proposed. It is shown that this guarantees that the phase transition will
occur within a specied range of values of p 2 , whatever the value of n. Since Model
D is otherwise unchanged, this modication does not require any change to the way
in which the constraint matrices are generated, unlike Model E.
4 Backtrack-Free Search
A CSP instance can be solved, or it can be proved that there is no solution, by a
complete search algorithm, for instance a simple backtracking algorithm (BT). This
algorithm attempts to build up a consistent solution to the CSP by considering
each variable in turn, and trying to assign a value to it which is consistent with
the existing assignments. If a consistent value is found, the next variable is tried;
otherwise, BT backtracks to the most recently assigned variable which still has an
untried value, and tries a dierent value for it. The algorithm proceeds in this
fashion until either a complete solution is found or every possible value for the rst
variable has been tried without success, in which case the problem has no solution.
A transition from satisable to unsatisable instances has been observed in
random binary CSPs if, for constant n, m and p 1 , a large number of hn; m;
instances are generated at each of a range of values of p 2 and each instance is
solved using an algorithm such as BT. Figure 1 shows the typical pattern seen
if the average search cost is computed for each value of p 2 . Here, the number
of consistency checks, i.e. the number of references to an element of a constraint
matrix, is used as the measure of search cost. Similar behaviour has been seen
for a wide range of parameter values and complete search algorithms, as shown for
instance in [13].
In

Figure

1, the instances were generated using Model B, but there is little difference
in the average cost curves between Models A, B, C and D. The maximum
average cost occurs where approximately half of the generated instances have solutions
and half do not, i.e. around the crossover point, where the probability that a
random instance has a solution is 0.5. There is a narrow region around the peak
where the generated populations contain a mixture of satisable and unsatisable
instances; for smaller values of p 2 , all the instances can be solved, and are increasingly
easy to solve as the constraints become looser; for larger values of p 2 , none
of the instances have solutions, and as the constraints become tighter, they are
increasingly easy to prove unsatisable.
In the 'easy-satisable' region, Figure 1 shows a point where the gradient of the
median curve changes, at approximately. This is also a kind of crossover
point: it is the point where the algorithm can solve 50% of the generated instances
without backtracking. In other words, in 50% of instances, as each variable is
considered, there is a value consistent with the past assignments, and the algorithm
never has to return to a previous variable. Unlike the solubility crossover point,
this is algorithm-dependent. More e-cient algorithms than BT, such as forward
checking [9], which considers the eect of each assignment on the variables not yet
assigned, can avoid failures due to incorrect choices which BT cannot, and so solve
instances without backtracking at larger values of p 2 .
The region where most problems can be solved without backtracking by an
algorithm is a region of 'trivial satisability'. This might be viewed as roughly
complementary to the region of trivial unsatisability identied by Achlioptas et
al. Clearly, if an instance can be solved without backtracking, it has a solution.
Thus, the probability that a random instance can be solved without backtracking is
a lower bound on the probability that it has a solution, and the constraint tightness
at which the probability of backtrack-free search is 0.5 is a lower bound on the
crossover point. Figure 1 suggests that for BT this bound will not be very tight.
However, it has the advantage that it can be calculated, as will be shown below.
Consistency
checks
Constraint tightness (p2)

Figure

1: Median cost of solving Model B problems with
using BT - 10,000 problems per p 2
If we can generate instances in such a way that the probability of backtrack-free
search is always positive for some range of values of p 2 , for all values of n, we shall no
longer have the situation where almost all problems become trivially unsatisable
for su-ciently large values of n. This would then be the rst step towards a CSP
model which gives an interesting asymptotic phase transition.
For Model D, the probability that BT can solve a problem without backtracking
can be calculated. This is given in [15] for complete constraint graphs. For incomplete
constraint graphs, if the variables are instantiated in the order
the probability that there is at least one value in the domain of variable i which is
consistent with the assignment already made is:
where d i is the past degree of variable i, i.e. the number of variables in
which constrain it. This is so because the nogoods in the constraint matrices are
generated independently. The probability that at least one value of every variable
is consistent with the previous assignments is:
Y
Let w be the maximum past degree of any variable in this ordering, i.e. the width
of the ordering. Then
Y
Y
There is a well-known algorithm for nding a ordering of the nodes with minimum
width [3], and Dyer and Frieze have shown that the minimum width of a
random graph is almost surely bounded by the average degree of the graph 1 . Experimental
results suggest that in randomly generated graphs, even of small size,
the minimum width will be strictly less than the average degree, unless the graph is
complete (in which case, of course, the width of any ordering is equal to the degree)
or extremely sparse.
We can therefore use (1 (1 q d
d is the average degree, as a lower
bound on the probability of backtrack-free search using BT. If we can ensure that
the value of this is at least 0.5 for some xed value of the constraint tightness, for
all n, we know that the true probability of backtrack-free search at that constraint
tightness is at least 0.5, and hence we have the required region of trivial solubility.
How do we keep (1 (1 q d
constant at a specied value of p 2 , when n
is increasing? To achieve this, (1 q d
must decrease, and hence either m must
increase or d must decrease. Intuitively, if the number of variables, n, increases
while the other parameters are kept constant, it becomes harder to nd a value for
every variable satisfying the constraints between it and the past assignments. This
can be compensated for by increasing the probability that an individual variable
is consistent with the past assignments, either by increasing the variable's domain
size, or by decreasing the number of past variables which constrain it. Decreasing
the average degree of the constraint graph as n increases is not a desirable option,
as it will eventually result in the graph being disconnected, so m must increase.
5 Upper bound on the crossover point
As shown in the last section, a lower bound on the crossover point is given by the
constraint tightness, ~
which the probability of backtrack-free search using BT
is at least 0.5. An upper bound, ^
given by the value for which the expected
number of solutions, E(N), is 0.5; for any p 2 the probability that there is a
solution is at most 0.5.
For the standard models for random binary CSPs,
we consider the value of p 2 at which E(N) = 1, we must have It
is clear that if m is increasing and d is constant, then to satisfy this equation, p 2
must also increase; as 1. Hence, the upper bound on the crossover
increase and we shall therefore not be able to show that there is a
range of values of the constraint tightness for which instances are unsatisable, with
high probability. To ensure that ^
does not increase with m, d must also increase.
However, bearing in mind the intuition given at the end of the last section, d must
not increase so fast that the region of trivial solubility disappears; increasing d and
makes instances more likely to have no solution, whereas increasing m makes
them more likely to have a solution, and a balance must be struck.
There is already evidence, in fact, that increasing m and d arbitrarily with n will
not necessarily lead to an asymptotic phase transition. In [14], the class of problems
problems in which and the constraint graph is
complete. For these problems, the crossover point ! 0 as n ! 1. Although the
number of values for each variable is increasing, the degree of the constraint graph
is also increasing (d = n 1), and too fast to allow instances to remain satisable.
6 A Proposed Scheme
To conne the crossover point between values of p 2 which are either constant or
converging as n increases, both m and d must increase with n. In order to keep as
Personal communication: this is a consequence of results in [12].
close as possible to the experimental use of existing models, in which m and p 1 or
d are xed, it is desirable to increase d and m only slowly with n.
Suppose we have a base population of problems, dened by the parameters
which will give the initial value of ~ p 2 , say ~
To increase d slowly with
n, suppose it grows as log n, e.g. a is a constant, and c is
determined by n 0 ; d 0 and a. Since almost every random graph with (a=2)n log n
edges is connected if a > 1, we should choose a > 1. If the constraint graph
is disconnected, each component of the graph forms a CSP, and these would in
practice be solved separately, so that in generating random instances it is a realistic
requirement that the constraint graph should be connected.
m is dened so that for any value of n, the lower bound on the crossover point
is and d are related
as just described. This ensures that, for all n, instances with p 2  ~
2 are trivially
satisable, with probability at least 0.5. To ensure an asymptotic phase transition,
the upper bound on the crossover point, ^
should have a limiting value as n !1
which is strictly < 1. This will ensure that there is, asymptotically, a region where
instances have no solution, for all n. However, since m and d are now dened in
terms of n, nothing further can be done to ensure the required behaviour; it only
remains to be seen whether the instances generated do in fact behave in this way.
7 Asymptotic Behaviour
First, calculations using dierent base populations and dierent values of a suggest
that increasing m and d with n as proposed does give the required behaviour. Figure
base population with
5, for a range of values of a. If a is small, i.e. d is increasing extremely slowly with
increases initially with n. However, Figure 2 suggests that it does eventually
decrease, so that there is a range of values of p 2 for which unsatisable instances
occur. By construction, the lower bound on the crossover point, given by ~
constant for all n, and hence the probability that an instance has a solution, p sat ,
is at least 0.5 for
n. The empirical evidence therefore suggests that
there is, asymptotically, a phase transition somewhere between ~  2 and the limiting
value of ^
which is < 1.
If this scheme were to be used to generate Model D instances for small values
of n, there are some practical considerations which would need to be taken into
account. Specically, m must be an integer, and nd must be an even integer, since
the number of constraints is nd=2. Having calculated d from d = a log n+c, it might
then be necessary to adjust it slightly. Then, rather than choosing m as above, a
possible choice is the smallest integer such that (1 (1 (1 ~
0:5. The
upper bound on the crossover point would not then follow exactly the curves shown
in

Figure

2, when n and a are such that m is small, and the lower bound on the
crossover point would not be constant at ~
2 . However, since the principal concern
here is with asymptotic behaviour, these variations when the values are small do
not signicantly aect the argument.
To show that the proposed scheme does give the required asymptotic behaviour,
we need to show what happens to the upper bound on the crossover point. Suppose
that
2 is the constraint tightness for which the expected number of solutions is ,
for 0 <  < 1. Then for
Upper
bound
on
crossover
point

Figure

2: Calculated upper bound on crossover point, from a base population with
Hence, log ^
and d is given by:
It can be shown (see Appendix A.1) that
lim
For instance, for the problems shown in Figure 2, ~
Since  can be arbitrarily close to 0, we have
lim
Note that the limiting value of ^
does not depend on a, although Figure 2 shows
that the value of a does aect the rate of convergence.
By increasing m and d with n as specied, we can therefore ensure that for all n,
the value given by the base population, and lim n!1 p
Hence, asymptotically there is a crossover point between
these two values of the constraint tightness, and we do have an asymptotic phase
transition with this scheme.
Furthermore, both d and m can increase quite slowly with n, so that for the
range of problem sizes that are likely to be solvable in practice, this scheme will be
close to schemes in which m and d are constant. This depends on the value of a; if
a is large, d increases relatively rapidly with n, and m also increases very fast, and
will become larger than n. Figure 3 shows that for the base population shown in
100 1000 10000 100000 1e+06
m/n

Figure

3: Ratio of m to n, from a base population with

Figure

2, m becomes much larger than n, and appears to increase without limit, if
a  7:5. m remains smaller than n for a  5, and m=n rapidly approaches 0 for
a  2:5.
It can be shown (Appendix A.2) that
lim
For the populations shown in Figure 2, ~  so that lim n!1
a  6:934, which accords with Figure 3.

Figure

2 suggests that choosing a large value of a will give more rapid convergence
of the upper bound on the crossover point. On the other hand, m will then
grow much faster than n, giving problems very dierent from the instances normally
generated in experimental studies. For the initial parameters used in Figures 2 and
3, a value of a around 2.5 would give an upper bound on the crossover point which
is always less than its initial value, and a rapid decrease in the ratio m=n. Hence,
such a scheme has a guaranteed asymptotic crossover point but is not too dissimilar
at experimental sizes from a scheme with m and d constant.
8 Related Work
A similar scheme was proposed independently by Xu and Li [17] for Model B. Their
scheme also applies to non-binary constraints. In the binary case, the constraint
graph has (a=2)n log n edges, using the notation of this paper. The number of values
in each variable's domain is n
, for constant
The constraint tightness, p 2crit , at which E(N) = 1 has been used as a predictor
of the crossover point [16, 14]. In Xu and Li's scheme, p
=a . They
show, by considering the second moment, E(N 2 ), that if
> 1=2 and e 2
=a  1=2
then
lim
Since
> 1=2 and e 2
=a  1=2, a  2
1:4427. Hence there
is a range of acceptable values of a between 1 and 1.4427, for which the constraint
graphs are connected, and similarly a range of values of
between 0 and 1/2, where
Xu and Li's result does not apply, as far as the lower limit on the crossover point
is concerned. It is still true, however, that lim n!1 p
=a .
If we assume Model D rather than Model B, we can use the probability of
backtrack-free search, as in section 4, whether or not a and
have values in the
ranges to which Xu and Li's result applies. Hence, it can be shown that there must
still be a crossover point asymptotically, even if we cannot prove its precise location.
It can be shown (see Appendix A.3) that
lim
=a
and hence there is a crossover point, for
=a and 1 e 2
=a , even
when Xu and Li's result does not apply. It is worth noting that the relationship
between the upper and lower bounds on the crossover point is the same as found
previously in section 7.
Models B and D dier only in the generation of the constraint matrices; p 2 is the
proportion of nogoods in each matrix in Model B and the probability that a pair of
values is nogood in Model D. Since a Model B population is more homogeneous than
a Model D population, it seems likely that if Model D has an asymptotic crossover
point then so does Model B. However, this needs to be conrmed before it can be
assumed that the result just given applies to Xu and Li's scheme. On the other
hand, it was shown in [14] that Models A and B are not equivalent asymptotically,
so the results of this paper may not transfer to all the standard models.
9 Conclusions
It has been shown that it is possible to ensure an asymptotic crossover point in one
of the standard random binary CSP models, Model D, by increasing other parameters
of the model with the number of variables. This counters the objections raised
by Achlioptas et al. to these models, that asymptotically almost all instances are
trivially unsatisable. Hence, it is not necessary to change the way in which the
constraint matrices are generated in order to produce asymptotically interesting
behaviour. However, since there is an asymptotic phase transition in graph colour-
ing, for a xed number of colours, the lack of structure in random constraints does
make a signicant dierence to asymptotic behaviour. In random binary CSPs,
unless the number of values increases with the number of variables, there cannot
asymptotically be a region where almost all problems are satisable, whereas in
graph colouring problems, the number of values is the number of colours and by
denition xed.
The probability that a random instance can be solved without backtracking by
a simple search algorithm has been used to give a lower bound on the crossover
point, and this is novel in studies of phase transitions in CSPs. Although not a
very tight bound and unlikely to be useful for predicting the exact location of the
crossover point, it is adequate to show that there is a region of trivial satisability.
Xu and Li [17] have considered a similar scheme for increasing the parameters of
Model B with the number of variables. This is somewhat simpler than the scheme
considered in this paper, although it has two parameters (
a) rather than one (a).
[17] does not give any motivation for this scheme, but it has the great advantage
that, except over a certain range of valuers of the parameters, the location of the
asymptotic phase transition can be exactly determined. In section 8, it is shown
that in Model D, this scheme gives an asymptotic crossover point between xed
values of the constraint tightness even outside the range of parameters identied
by Xu and Li. Further work to show whether Models B and D are asymptotically
similar would be useful, as well as further study of the asymptotic phase transition
where Xu and Li's results does not apply. It may be that the range of parameter
values for which the asymptotic phase transition can be exactly located indicates
qualitatively dierent asymptotic behaviour from the range where their result does
not hold.

Acknowledgments

The author is a member of the APES research group (http://www.cs.strath.ac.uk/~apes)
and wishes to thank the other members. Thanks are also due to Alan Slomson for
the lemma given in Appendix A.3 and to Martin Dyer and Alan Frieze for the
results on the width of random graphs.



--R

Random Constraint Satisfaction - A More Accurate Picture
Where the Really Hard Problems are.

In search of the best constraint satisfaction search.
Random Constraint Satisfaction: Flaws and Structure.

The Phase Transition Behaviour of Maintaining Arc Consistency.
The Phase Transition Behaviour of Maintaining Arc Consistency.
Increasing tree search e-ciency for constraint satisfaction problems
The Hardest Constraint Problems: A Double Phase Transition.
Random Constraint Satisfac- tion: Theory meets Practice
Sudden Emergence of a Giant k-Core in a Random Graph
An empirical study of phase transitions in binary constraint satisfaction problems.
Locating the Phase Transition in Constraint Satisfaction Problems.
Modelling Exceptionally Hard Constraint Satisfaction Problems.
Exploiting the Deep Structure of Constraint Prob- lems
Exact Phase Transitions in Random Constraint Satisfaction Problems.
--TR
In search of the best constraint satisfaction search
The hardest constraint problems
Exploiting the deep structure of constraint problems
Sudden emergence of a giant <italic>k</italic>-core in a random graph
A Sufficient Condition for Backtrack-Free Search
Results related to threshold phenomena research in satisfiability
Lower bounds for random 3-SAT via differential equations
Random Constraint Satisfaction

--CTR
Martin Dyer , Alan Frieze , Michael Molloy, A probabilistic analysis of randomly generated binary constraint satisfaction problems, Theoretical Computer Science, v.290 n.3, p.1815-1828, 3 January
S. Durga Bhavani , Arun K. Pujari, EvIA - Evidential Interval Algebra and Heuristic Backtrack-Free Algorithm, Constraints, v.9 n.3, p.193-218, July 2004
Ke Xu , Wei Li, Many hard examples in exact phase transitions, Theoretical Computer Science, v.355 n.3, p.291-302, 14 April 2006
Alan Frieze , Michael Molloy, The satisfiability threshold for randomly generated binary constraint satisfaction problems, Random Structures & Algorithms, v.28 n.3, p.323-339, May 2006
Ke Xu , Frdric Boussemart , Fred Hemery , Christophe Lecoutre, Random constraint satisfaction: Easy generation of hard (satisfiable) instances, Artificial Intelligence, v.171 n.8-9, p.514-534, June, 2007
Ian P. Gent , Ewan Macintyre , Patrick Prosser , Barbara M. Smith , Toby Walsh, Random Constraint Satisfaction: Flaws and Structure, Constraints, v.6 n.4, p.345-372, October 2001
random problems;constraint satisfaction;phase transitions