text:
# The dynamics of proving uncolourability of large random graphs I. Symmetric Colouring Heuristic

## 1 Introduction

The wide variety of practical problems that can be mapped onto NP-complete problems, together with the challenge in finding an answer to one of the most important open questions in theoretical computer science, ‘Does $`NP=P\mathrm{?}`$’, have led to intensive studies in the past decades. Despite intense efforts, the worst case running times of all currently known algorithms grow exponentially with the size of the inputs to these problems. However, NP-complete problems are not always hard. They might be even easy to solve on average  i.e. when their resolution complexity is measured with respect to some underlying probability distribution of instances. This ‘average-case’ behavior depends, of course, on the input-distribution.

In the graph colouring problem, one of the most well-known combinatorial optimization problems with applications ranging from time tabling and scheduling , through register allocation , to frequency assignment , the average-case behavior is often defined on random graphs. The aim is to colour the vertices of the graph such that no adjacent vertices have the same colour. Whether this can be done with $`k`$ or less than $`k`$ colours constitutes the so called $`k`$-colouring ($`k`$-COL) decision problem. $`2`$-COL is easy and can be decided in a time growing polynomially with the size (number of vertices) of the graph, while $`k`$-COL is NP-complete for any $`k3`$ . We shall restrict to the investigation of 3-COL in the following, and denote by Red (R), Green (G) and Blue (B) the available colours. Graphs will be generated according to the $`G(N,p)`$ distribution: they are made of $`N`$ vertices, linked two by two through edges with probability $`p`$. Studies of the 3-COL problem on this ensemble have indicated that, for sparse random graphs in which $`p=c/N`$, a phase transition between colourable and uncolourable phase occurs in the large $`N`$ limit as the connectivity (average vertex–degree) $`c`$ is varied $`c`$ . Below a critical value $`c_3`$ of the connectivity $`c`$, almost all instances are colourable whereas, above $`c_3`$, the probability that an instance is colourable drops to zero. Determination of $`c_3`$ is an open question in random graph theory first posed by Erdös . Nevertheless, years of investigation have yielded some lower and upper bounds for $`c_3`$. Probabilistic counting arguments have led to the best known upper bound $`c_3<4.99`$ . A recent analysis of a “smoothed” version of the Brelaz heuristic  has yielded the highest lower bound $`c_3>4.03`$ .

In a recent work, Mulet et al. used a mapping of the graph colouring problem onto the Potts model, and applied statistical mechanics methods to estimate $`c_3`$ . The result, $`c_34.69`$, is very close to numerical simulations . Below $`c_3`$, solving 3-COL can be done by exhibiting a proper colouring, a task carried out by search algorithms in an apparently efficient way . Above $`c_3`$, resolution of an instance almost surely means exhibiting a proof of its uncolourability, a very hard task. One of the most popular algorithm capable of exhibiting such proofs is the Davis-Putnam-Logemann-Loveland procedure (DPLL) . Its operation amounts to a clever exhaustive search in the configuration space, based on the errors and trials principle. Generally, the time needed by DPLL to check the absence of colouring grows exponentially with the size of the graph, $`T\mathrm{exp}(N\omega (c))`$. The purpose of this paper is to calculate $`\omega `$ as a function of $`c`$. Such a study was recently undertaken for the satisfiability problem  and vertex covering , both hard decision problems. The interest of 3-COL with respect to the latter cases is its intrinsic symmetry. From any proper colouring, five other colourings can be deduced through colour permutations. It is therefore interesting to understand whether respecting or breaking this symmetry can lead to computational gains, and how this can be implemented in the dynamics of the search algorithm .

Hereafter, we focus on the case of colouring heuristics that do not explicitly break the symmetry between colours. The analysis of the biased case is left to a forthcoming companion paper . This article is organized as follows. The colouring algorithm is presented in section 2. Section 3 is devoted to the analysis of the dynamics and of the resolution time of the algorithm. In the last section 4 we summarize and propose some perspectives.

## 2 Description of the Colouring Algorithm

The algorithm which we analyze in this paper is a complete algorithm capable of determining whether a given graph is $`3`$-colourable or not. The algorithm is based on a combination of a colouring heuristic, $`3`$-GREEDY-LIST ($`3`$-GL), and of backtracking steps. Its operation is exposed below.

### 2.1 Operation of the Greedy-List algorithm with backtracking

The action of the colouring procedure is illustrated on Figure 1 and described as follows:

* Necessary Information: while running, the algorithm maintains for each uncoloured vertices, a list of available colours, which consists of all the colours that can be assigned to this vertex given the colours already assigned to surrounding vertices.
* Colouring Order: the order in which the vertices are coloured, is such that the most constrained vertices i.e. with the least number of available colours are coloured first. At each time step, a vertex is chosen among the most constrained vertices, and its colour is selected from the list of its available colours. Both choices are done according to some heuristic rule, which can be unbiased (no preference is made between colours), or biased (following a hierarchy between colours), see next Section.
* List-Updating: to ensure that no adjacent vertices have the same colour, whenever a vertex is assigned a colour, this colour is removed from the lists (if present) attached to each of the uncoloured neighbors.
* Contradictions and Backtracking: a contradiction occurs as soon as one of the lists becomes empty. Then, the algorithm backtracks to the most recently chosen vertex, which have more than one available colour (the closest node in the search tree - see definition below).
* Termination Condition: the algorithm stops when all vertices are coloured, or when all colouring possibilities have been tried.

A search tree describes the action of the algorithm is the following, with the following components:

* Node: a node in the tree represents a vertex chosen by the algorithm, which has more than one colour in its available-colours-list.
* Edge: an edge which comes out of a node, corresponds to a possible colour of the chosen vertex.
* Leaf: a branch terminates either by a solution (denoted by $`S`$) or by a contradiction (denoted by $`C`$), depending on whether the colour choices made along this branch give a proper colouring of the graph, or not.

### 2.2 Colour symmetry: the unbiased 3-GL heuristic

Let us call 3-GL heuristic the incomplete version of the above algorithm, obtained when the algorithm stops if a colouring is found (and outputs “Colourable”), or just after the first contradiction instead of backtracking (and outputs “Don’t know if colourable or not”). In contrast to 3-GL algorithm with backtracking, the 3-GL heuristic is not able to prove the absence of solution, and is amenable to rigorous analysis .

In the simplest case, vertices and colours are chosen purely randomly without any bias between colours (Colouring Order step described above). This ‘symmetric’ 3-GL heuristic verifies two key properties which our analysis rely on. The first one is a statistical invariance called R-property. Throughout the execution of the algorithm, the uncoloured part of the graph is distributed as $`G((1t)N,p)`$ where $`t`$ is the number of coloured vertices divided by $`N`$. The second property is colour symmetry. The search heuristic is symmetric with respect to the different colours, and the initial conditions are symmetric as well. Denoting by $`l=\{R,G,B\}`$ the list of the three available colours, a $`2`$-colour node can have one of three possible lists $`\{R,G\}`$,$`\{R,B\}`$,$`\{G,B\}`$ and similarly, there are three possible lists for a $`1`$-colour node. Due to colour symmetry, in the limit of large $`N`$, we expect the groups of $`1`$-colour and $`2`$-colour vertices to be composed of an equal number of vertices (with $`o(N)`$ fluctuations) with the three kinds of lists. Hence, in the leading order, the evolution of the algorithm can be expressed by the evolution of the three numbers $`N_j(T)`$ of $`j`$-colour nodes ($`j=1,2,3`$). The analysis of the evolution of these numbers in the course of the colouring was done by Achlioptas and Molloy. It is briefly recalled below.

### 2.3 Analysis of the symmetric 3-GL heuristic

In the absence of backtracking, 3-GL terminates as soon as a contradiction occurs, or a solution is found. Differential equations can be used to track the evolution of node populations as colouring proceeds . In this section we briefly recall how to obtain these differential equations, and the associated search trajectories of the heuristic in terms of node populations.

According to the R-property, the probability that an $`j`$-colour node is a neighbour of the currently coloured node equals $`c/N`$ throughout the running of the heuristic. The probability that the same colour appears in its list is $`j/3`$. Therefore the two average flows of vertices, $`w_2(T)`$ from $`N_3(T)`$ to $`N_2(T)`$, and $`w_1(T)`$ from $`N_2(T)`$ to $`N_1(T)`$ are $`cN_3(T)/N`$ and $`2cN_2(T)/(3N)`$ respectively. Hence, the evolution equations for the three populations of vertices read,

$`N_3(T+1)`$ $`=`$ $`N_3(T)w_2(T),`$
$`N_2(T+1)`$ $`=`$ $`N_2(T)+w_2(T)w_1(T)\delta N_1(T),`$
$`N_1(T+1)`$ $`=`$ $`N_1(T)+w_1(T)(1\delta N_1(T)).`$ (1)
where $`\delta N_1(T)=1`$ if $`N_1(T)=0`$ (a $`2`$-colour vertex is coloured) and $`\delta N_1(T)=0`$ if $`N_1(T)0`$ (a $`1`$-colour vertex is coloured). For $`c>1`$, both $`N_2(T)`$ and $`N_3(T)`$ are extensive in $`N`$, and can be written as

$$N_i(T)=n_i(T/N)N+o(N).$$
(2)
Apparition of the reduced time, $`t=T/N`$, means that population densities $`n_i(T/N)`$ change by $`O(1)`$ over $`O(N)`$ time intervals. To avoid the appearance of contradictions, the number of $`1`$-colour vertices must remain of $`O(1)`$ throughout the execution of the algorithm. From queueing theory, this requires $`w_1(t)<1`$, that is

$$\frac{2}{3}cn_2(t)<1$$
(3)
which means that $`1`$-colour nodes are created slowly enough to colour them and do not accumulate. Thus, in the absence of backtracking, the evolution equations for the densities are

$$\frac{dn_3(t)}{dt}=cn_3(t),\frac{dn_2(t)}{dt}=cn_3(t)1.$$
(4)
The solution of these differential equations, with initial conditions $`n_3(0)=1`$, $`n_2(0)=0`$, is

$$n_3(t)=e^{ct},n_2(t)=1te^{ct}.$$
(5)
Eqs. (4) were obtained under the assumption that $`n_2(t)>0`$ and hold until $`t=t_2`$ at which the density $`n_2`$ of 2-colour nodes vanishes. For $`t>t_2`$, $`2`$-colour vertices do not accumulate anymore. They are coloured as soon as they are created. $`1`$-colour vertices are almost never created, and the vertices coloured by the algorithm are either $`2`$-, or $`3`$-colour vertices. Thus, when $`t_2<t<1`$, $`n_2(t)=0`$, and $`n_3(t)=1t`$ decreases to zero. A proper coloring is found at $`t=1`$ i.e. when all nodes have been coloured.

These equations define the trajectory of the algorithm in phase space in the absence of contradictions i.e. as long as condition (3) is fulfilled. The trajectory corresponding to $`c=3`$ is plotted on Figure 2. For $`c<c_L3.847`$, condition (3) is never violated, and the probability that the algorithm succeeds in finding an appropriate colouring without backtracking is positive. The complexity $`\gamma (c)N`$ of the algorithm in this regime of $`c`$ is linear with $`N`$, and equals the number of nodes in the single branch of the search tree.

$$\gamma (c)=1\frac{2}{3}c_0^t^{}𝑑tn_2(t),$$
(6)
where $`t^{}>0`$ is the first time (after $`t=0`$) that $`n_2(t)`$ becomes $`0`$.

For $`c>c_L`$ condition (3) is violated at $`t=t_d(c)`$ which depends on $`c`$, and $`1`$-colour vertices start to accumulate. As a result, the probability for contradictions becomes large, and backtracking enters into play.

## 3 Study of the 3-Greedy List algorithm with backtracking

The analytical study of the complexity in the presence of backtracking is inspired from previous analysis of random 3-SAT solving with DPLL algorithm .

### 3.1 Evolution equation for the search process

In the absence of solution, the algorithm builds a complete search tree before stopping. In a complete tree $`Q+1=B`$, where $`B`$ is the number of leaves and $`Q`$ the number of nodes. This relation implies that the key for obtaining the complexity $`Q`$ lies in the calculation of $`B`$. In order to enable a mathematical analysis of $`B`$, we rely on the fact that the search tree is complete, and therefore the sequential (depth-first) way in which the algorithm builds it is irrelevant to the final structure. In other words, the order in which the available colours of a vertex are tried, does not affect the final shape of the tree. An identical tree can be built in a parallel (breadth-first) way defined as follows, and illustrated in Figure 3.

At time $`T=0`$, the tree reduces to a root node, to which is attached the graph to colour, and an attached outgoing edge. At time $`T`$, that is, after having coloured $`T`$ vertices of the graphs attached to each branch, the tree is made of $`\stackrel{~}{B}(T)(2^T)`$ branches, each one carrying a partially coloured graph. At next time step $`TT+1`$, a new layer is added to the tree by colouring, according to 3-GL heuristic, one more vertex along every branch. As a result, at each instant of the parallel process, branches either die (encounter a contradiction), keep growing (a $`1`$-colour vertex is coloured), or split (a $`2`$-colour vertex is chosen and its two available colours are tried simultaneously) (Figure 3). This parallel growth process is Markovian, and can be encoded in an instance–dependent (and exponentially large in $`N`$) evolution matrix $`H`$ .

To obtain a tractable expression for $`H`$, we neglect correlations arising from the choice of the same vertex in two different branches. After assigning $`T`$ variables, each branch represents a different sequence of $`T`$ coloured vertices, which determines the values $`\{N_1,N_2,N_3\}`$ attached to this branch. Denoting by $`\stackrel{~}{B}(N_1,N_2,N_3;T)`$ the number of branches at time $`T`$ with $`N_i`$ ($`i=1,2,3`$) $`i`$-colour vertices, the growth process of the search tree can be described by the evolution of $`\stackrel{~}{B}(N_1,N_2,N_3;T)`$ with time. This evolution is given by

$$\stackrel{~}{B}(N_1,N_2,N_3;T+1)=\underset{N_1^{},N_2^{},N_3^{}=0}{\overset{\mathrm{}}{}}H(N_1,N_2,N_3,N_1^{},N_2^{},N_3^{};T)\stackrel{~}{B}(N_1^{},N_2^{},N_3^{};T),$$
(7)
where

$`H(N_1,N_2,N_3,N_1^{},N_2^{},N_3^{};T)={\displaystyle \underset{w_2=0}{\overset{N_3^{}}{}}}\left({\displaystyle \genfrac{}{}{0pt}{}{N_3^{}}{w_2}}\right)({\displaystyle \frac{c}{N}})^{w_2}(1{\displaystyle \frac{c}{N}})^{N_3}\delta _{N_3^{}N_3w_2}\times `$
$`\{(1\delta _{N_1^{}}){\displaystyle \underset{w_1=0}{\overset{N_2^{}}{}}}\left({\displaystyle \genfrac{}{}{0pt}{}{N_2^{}}{w_1}}\right)({\displaystyle \frac{2c}{3N}})^{w_1}(1{\displaystyle \frac{2c}{3N}})^{N_2^{}w_1}\delta _{N_2N_2^{}(w_2w_1)}\delta _{N_1N_1^{}w_1+1}+`$
$`2\delta _{N_1^{}}{\displaystyle \underset{w_1=0}{\overset{N_2^{}1}{}}}\left({\displaystyle \genfrac{}{}{0pt}{}{N_2^{}1}{w_1}}\right)({\displaystyle \frac{2c}{3N}})^{w_1}(1{\displaystyle \frac{2c}{3N}})^{N_2^{}w_11}\delta _{N_2N_2^{}(w_2w_11)}\delta _{N_1N_1^{}w_1}\}`$ (8)
is the branching matrix of the $`3`$-GL algorithm, and $`\delta N`$ is the Kronecker delta function. The matrix describes the average number of branches with $`\{N_i\}_{i=1}^3`$ $`i`$-colour vertices, which are coming out from branches with $`\{N_i^{}\}_{i=1}^3`$ $`i`$-colour vertices, as a result of all the colouring options of the vertex coloured at time $`T`$. The R-property is responsible for the binomial distributions of the flows $`w_1`$ and $`w_2`$ in (8). Note that (8) is written under the assumption that no $`3`$-colour nodes are chosen by the algorithm throughout the growth process. This assumption is consistent with the resultant solution which shows that in the uncolourable (UNCOL) region, $`n_2(t)`$, namely the number of 2-colour vertices divided by $`N`$, keeps positive for all $`t>0`$.

### 3.2 Resolution of the evolution equation

In order to obtain the complexity from the evolution equation of $`\stackrel{~}{B}(\stackrel{}{N};T)`$ (7), we define the generating function $`B(\stackrel{}{y};T)`$ of $`\stackrel{~}{B}(\stackrel{}{N};T)`$ to be

$$B(\stackrel{}{y};T)=\underset{\stackrel{}{N}}{}\mathrm{exp}(\stackrel{}{y}\stackrel{}{N})\stackrel{~}{B}(\stackrel{}{N};T),\stackrel{}{y}=(y_1,y_2,y_3),\stackrel{}{N}=(N_1,N_2,N_3).$$
(9)
Plugging (8,9) into (7) yields the following evolution equation for the generating function $`B(\stackrel{}{y};T)`$,

$$B(\stackrel{}{y};T+1)=e^{y_1}B(\stackrel{}{g}(\stackrel{}{y});T)+\left(2e^{y_2}e^{y_1}\right)B(\mathrm{},g_2(\stackrel{}{y}),g_3(\stackrel{}{y});T),$$
(10)
where

$`g_1(\stackrel{}{y})`$ $`=`$ $`y_1,`$
$`g_2(\stackrel{}{y})`$ $`=`$ $`y_2+{\displaystyle \frac{2c}{3N}}\left(e^{y_1y_2}1\right),`$
$`g_3(\stackrel{}{y})`$ $`=`$ $`y_3+{\displaystyle \frac{c}{N}}\left(e^{y_2y_3}1\right).`$ (11)
To solve (10), we make scaling hypothesis for $`\stackrel{~}{B}`$ and $`B`$ in the large $`N`$ limit. Let us examine how a step of the algorithm affects the size of the three populations $`N_1,N_2,N_3`$. Since the average connectivity is $`O(1)`$ i.e. each vertex is connected on average only to $`O(1)`$ vertices, when a vertex is coloured, the number of vertices whose status (the number of available colours) is subsequently changed is bounded by the number of neighbors of the coloured vertex. Hence a reasonable assumption is that the densities $`n_i=N_i/N`$ change by $`O(1)`$ after $`T=t\times N`$ vertices are coloured. The corresponding Ansatz for the number of branches is,

$$\stackrel{~}{B}(\stackrel{}{N};T)=e^{N\omega (n_1,n_2,n_3;t)+o(N)}$$
(12)
where non-exponential terms in $`N`$ depend on the populations of $`i`$-colour nodes ($`i=1,2,3`$). From (12) and (9) we obtain the following scaling hypothesis for the generating function $`B`$,

$$B(\stackrel{}{y};T)=e^{N\phi (y_1,y_2,y_3;t)+o(N)},$$
(13)
where $`\phi (\stackrel{}{y};t)`$ is the Legendre transform of $`\omega (\stackrel{}{n};t)`$, the logarithm of the number of branches $`B(\stackrel{}{N};T)`$ divided by $`N`$,

$`\phi (\stackrel{}{y};t)`$ $`=`$ $`\underset{\stackrel{}{n}}{\mathrm{max}}\left[\omega (\stackrel{}{n};t)+\stackrel{}{y}\stackrel{}{n}\right]`$
$`\omega (\stackrel{}{n};t)`$ $`=`$ $`\underset{\stackrel{}{y}}{\mathrm{min}}\left[\phi (\stackrel{}{y};t)\stackrel{}{y}\stackrel{}{n}\right]`$ (14)
where $`\stackrel{}{n}=(n_1,n_2,n_3)`$. $`\stackrel{}{y}`$ and $`\stackrel{}{n}`$ are conjugated Legendre variables; in particular, the typical fraction of $`i`$-colour nodes at depth $`t`$ are given by the derivatives of $`\phi `$ at vanishing argument,

$$n_i(t)=\frac{\phi }{y_i}(\stackrel{}{y}=0;t).$$
(15)
At the initial stage of the tree building up, there is a single outgoing branch from the root node, carrying a fully uncoloured graph. Thus, $`\stackrel{~}{B}(\stackrel{}{N};T=0)=1`$ if $`\stackrel{}{N}=(0,0,N)`$, $`0`$ otherwise, and $`B(\stackrel{}{y},T=0)=e^{Ny_3}`$. The initial condition for function $`\phi `$ is simply,

$$\phi (\stackrel{}{y};t=0)=y_3.$$
(16)
According to (2) both $`N_2(T)`$ and $`N_3(T)`$ are extensive in $`N`$; hence $`n_2>0`$ and $`n_3>0`$. Conversely, as soon as $`N_1(T)`$ becomes very large, contradictions are very likely to occur, and the growth process stops. Throughout the growth process, $`N_1=O(1)`$ almost surely. Thus $`n_1=0`$ with high probability, and $`\phi `$ does not depend upon $`y_1`$ from (15).

Independence of $`\phi `$ on $`y_1`$ allows us to choose the latter at our convenience, that is, as a function of $`y_2,y_3,t`$. Following the so-called kernel method , we see that equation (10) simplifies if $`y_1=y_2\mathrm{ln}2`$. Then, from Ansatz (13), we obtain the following partial differential equation (PDE),

$$\frac{\phi }{t}(y_2,y_3;t)=y_2+\mathrm{ln}2\frac{c}{3}\frac{\phi }{y_2}(y_2,y_3;t)+c(e^{y_2y_3}1)\frac{\phi }{y_3}(y_2,y_3;t).$$
(17)
The solution of PDE (17) with initial condition (16) reads

$$\phi (y_2,y_3;t)=\frac{c}{6}t^2\frac{c}{3}t+(1t)(y_2\mathrm{ln}2)+\mathrm{ln}\left[3+e^{2ct/3}\left(2e^{y_3y_2}3\right)\right].$$
(18)
### 3.3 Growth process of the search tree

PDE (13) can be interpreted as a description of the growth process of the search tree resulting from the algorithm operation. Using Legendre transform (14), PDE (13) can be written as an evolution equation for the logarithm $`\omega (n_2,n_3;t)`$ of the average number of branches with densities $`n_2,n_3`$ of 2- ,3-colours nodes as the depth $`t=T/N`$ increases,

$$\frac{\omega }{t}=\frac{\omega }{n_2}+\mathrm{ln}2\frac{c}{3}n_2+cn_3\left[\mathrm{exp}\left(\frac{\omega }{n_3}\frac{\omega }{n_2}\right)1\right].$$
(19)
The surface $`\omega `$, growing with “time” $`t`$ above the plane $`n_2,n_3`$ describes the whole distribution of branches. Here, this distribution simplifies due to nodes conservation. The sum $`n_2+n_3`$ of 2- and 3-colour nodes densities necessarily equals the fraction $`1t`$ of not-yet coloured nodes. Therefore, $`\omega `$ is a function of $`n_3`$ and $`t`$ only, whose expression is obtained through inverse Legendre transform of (18),

$`\omega (n_3;t)`$ $`=`$ $`{\displaystyle \frac{c}{6}}t(12t4n_3)n_3\mathrm{ln}n_3(1n_3)\mathrm{ln}(1n_3)`$ (20)
$`(1tn_3)\mathrm{ln}2+(1n_3)\mathrm{ln}\left[3\left(1e^{\mathrm{\hspace{0.17em}2}tc/3}\right)\right].`$
Figure 4 exhibits $`\omega (n_3,t)`$ for $`c=10`$.

The average number of branches at depth $`t`$ in the tree equals

$$\stackrel{~}{B}(t)=𝑑n_2𝑑n_3e^{N\omega (n_2,n_3;t)}e^{N\omega ^{}(t)},$$
(21)
where

$$\omega ^{}(t)=\frac{c}{6}t^2\frac{c}{3}t(1t)\mathrm{ln}2+\mathrm{ln}\left[3e^{2ct/3}\right]$$
(22)
is the maximum over $`n_2,n_3`$ of $`\omega (n_2,n_3;t)`$ reached in $`n_2^{}(t),n_3^{}(t)`$. In other words, the exponentially dominant contribution to $`\stackrel{~}{B}(t)`$ comes from branches carrying partially coloured graphs with densities

$$n_3^{}(t)=\frac{2}{3e^{\mathrm{\hspace{0.17em}2}ct/3}1},n_2^{}(t)=1tn_3^{}(t).$$
(23)
Under the action of the $`3`$-GL algorithm, initially random $`3`$-colouring instances become random mixed $`2\&3`$-colouring instances, where nodes can have either 2 or 3 colours at their disposal. This phenomenon indicates that the action of the $`3`$-GL algorithm on random $`3`$-colouring instances can be seen as an evolution in the $`n_2,n_3`$ phase-space (Figure 2). Each point $`(n_2,n_3)`$ in this space, represents a random mixed $`2\&3`$-colouring instance, with an average number $`(n_2+n_3)N`$ of nodes, and a fraction $`n_3/(n_2+n_3)`$ of $`3`$-colour nodes. Parametric plot of $`n_2^{}(t),n_3^{}(t)`$ as a function of $`t`$ represents the trajectories of dominant branches in Figure 2.

The search tree keeps growing as long as no contradictions are encountered i.e. as long as $`1`$-colour vertices do not accumulate. This amounts to say that dominant branches are not suppressed by contradictions and become more and more numerous through 2-colour nodes colouring,

$$\frac{d\omega ^{}}{dt}(t)>0,$$
(24)
or equivalently from (19), $`n_2^{}(t)<3\mathrm{ln}2/c`$. This defines the halt condition for the dominant branch trajectories in the $`n_2,n_3`$ dynamical phase diagram of Figure 2. Call $`t_h`$ the halt time at which condition (24) gets violated. The logarithm $`\omega ^{}(t_h)`$ of the number of dominant branches at $`t=t_h`$, when divided by $`\mathrm{ln}2`$, yields our analytical estimate for the complexity of resolution, $`\mathrm{ln}Q/N`$.<sup>1</sup><sup>1</sup>1Let us stress that our calculation is approximate. First, as mentioned above, correlations between different branches have been neglected. Secondly, $`\phi `$ is the Legendre transform of $`\omega `$ over non-negative values of $`n_i`$ only, a constraint we have not taken into account in the growth PDE (17). We expect our prediction to be accurate when $`n_2`$ and $`n_3`$ are not getting to small throughout the growth process i.e. for large enough connectivites $`c`$.

### 3.4 Comparison with numerical experiments

To check our theory, we have run numerical experiments to estimate $`\omega `$, the logarithm of the median solving time, as a function of the initial graph degree $`c`$. Figure 5 describes the output of these simulations. The easy-hard-easy pattern of the GC problem when passing from the COL ($`c<c_3`$) to the UNCOL ($`c>c_3`$) regions is clearly visible, with an exponential scaling of hardness around the critical connectivity.

Table 1 presents results for $`\omega `$ as a function of the connectivity $`c`$ in the UNCOL phase as found from numerical experiments and from the above theory. Note the significant decrease in the complexity as the initial connectivity increases. Extrapolation of numerical results to the large $`N`$limit is described in the Inset of Figure 5. For $`c=7`$, the agreement between numerical and analytical results is not perfect. However, the high computational complexity of the algorithm for small $`c`$ values, does not allow us to obtain numerical results for large sizes $`N`$, and affect the quality of the large $`N`$ extrapolation of $`\omega `$.

In the UNCOL region, as $`c`$ increases, contradictions emerge in an earlier stage of the algorithm, the probability that the same vertex appears in different branches reduces, and the analytical prediction becomes exact. As a consequence of the early appearance of contradictions, the complexity $`\omega `$ decreases with $`c`$. At very large $`c`$, we find

$$\omega (c)\frac{3\mathrm{ln}2}{2}\frac{1}{c^2}\frac{1.040}{c^2},$$
(25)
and therefore that the (logarithm of the) complexity exhibits a power law decay with exponent $`2`$ as a function of connectivity $`c`$.

## 4 Summary and Discussion

In this study we have presented an analysis of the complexity of the $`3`$-Greedy List (GL) algorithm acting onto uncolourable (UNCOL) random-graph instances. This analysis provides an estimate of the typical performances of the GL algorithm. Above the colourability threshold $`c_3`$, proving the absence of colouring takes a time growing exponentially with the size $`N`$ of the graph. However, well above the threshold i.e. for graph connectivities $`cc_3`$, instances are strongly over-constrained, and the absence of proper colouring is established more and more quickly. Complexities in this region, though exponential with $`N`$, have a very small prefactor which for large values of $`c`$ vanishes with a power law behaviour ($`\omega (c)1.040/c^2`$).

The present study could be pursued in many directions. First, it would be interesting to analyse the performances of the 3-GL algorithm in the colourable (COL) phase $`c<c_3`$. Graphs with low connectivities ($`c<c_L`$) being almost surely coloured in a time growing linearly with their size , the interesting region is the intermediate range of connectivities, $`c_L<c<c_3`$. There, proper colourings are found at the cost of an exponential computational effort, which could in principle be quantitatively characterized along the lines of Ref.. Secondly, another interesting extension would be to focus on other search heuristics. Attractive candidates are heuristics that favor high-degree vertices. Such a procedure has been recently analyzed (in the absence of backtracking) to improve rigorous lower bounds to the COL-UNCOL threshold $`c_3`$ . Last, the study of more realistic e.g. finite dimensional graph distributions, could aid in the understanding of the influence of instance structure on resolution complexity.

As stated in the introduction, the main interest of 3-COL with respect to other NP-complete problems e.g. SAT lies in its global gauge symmetry. The 3-GL heuristic we concentrated on here does not break this symmetry in that it treats on a equal foot all 2-colours nodes when a split has to made, irrespectively of their attached list of available colors e.g. $`\{R,G\}`$, $`\{R,B\}`$ or $`\{G,B\}`$. It is easy to design heuristics that explicitly violates this symmetry and preferentially colour nodes with $`R`$ if possible. The analysis of the computational performances of backtracking algorithms based on such an asymmetric heuristic is technically quite difficult, and will be presented in a forthcoming work .

A promising outcome of the present work is the relative technical simplicity of our 3-GL analysis with respect to the corresponding studies of DPLL on random SAT instances. The growth partial differential equation monitoring the evolution of the search tree could be solved exactly, in contradistinction with previous studies of the SAT problem. This essentially comes from a simple conservation law, the sum of the numbers of coloured and uncoloured nodes remaining of course constant throughout the search, and makes 3-GL with backtracking a good candidate for future rigorous studies .

Acknowledgements

We would like to thank Simona Cocco for helpful discussions. This work was supported in part by the ACI Jeunes Chercheurs “Algorithmes d’optimisation et systèmes quantiques désordonnés”. L.E. acknowledges financial support from the post-doctoral funding program of the French Ministry of Research.

References