Algorithms for calculating R(5,5) and R(6,6) Calculating the Ramsey numbers R(5,5) and R(6,6) is a notoriously difficult problem. Indeed Erdős once said:

Suppose aliens invade the earth and threaten to obliterate it in a year's time unless human beings can find the Ramsey number for red five and blue five. We could marshal the world's best minds and fastest computers, and within a year we could probably calculate the value. If the aliens demanded the Ramsey number for red six and blue six, however, we would have no choice but to launch a preemptive attack. 

I am curious what algorithm we would employ if such a situation were to occur. I know analytic results have been used to put bounds on R(5,5) and R(6,6), but I am mostly interested in the problem from a computational perspective. If we were to set a computer to the task and let it run for however long it might take, what algorithm would we use? How many operations might we expect it to take/what would it's time complexity be?
Edit: I should clarify that I am seeking the best classical algorithm. It was after reading the paper that Carlo Beenakker cites using quantum annealing that I became interested in finding the best classical alternative.
 A: Well, it seems that quantum computers offer a peaceful alternative to the aliens threat, see Experimental determination of Ramsey numbers. (Here is a tutorial on this work.) "Experimental" refers to the nature of the algorithm, which solves an optimization problem to obtain the Ramsey number with some uncertainty. The cited reference has implemented this "quantum annealing algorithm" in a superconducting circuit (the D-wave machine), correctly finding $R(m,2)$ for $4\leq m\leq 8$ and $R(3,3)$. Progress in quantum computing is sufficiently rapid, that if the aliens won't show up until later this century, we stand a good chance.
Classical algorithms for Ramsey numbers are described in Computational methods for Ramsey numbers (2000) and in Problems of Unknown Complexity: Graph isomorphism and Ramsey theoretic numbers
 (2009). Indeed, the computational complexity of the calculation of Ramsey numbers is unknown.
A: I think Brendan McKay's paper $R(4,5) = 25$ with Stanisław Radziszowski (appeared as J. Graph Theory, 19 (1995) 309–322) on computing $R(4,5)$ will describe one possible approach. It is available as a pdf here for your downloading pleasure (Added by DR: or from the publisher at doi:10.1002/jgt.3190190304).
A: We could view $R(5,5)$ as a satisfiability problem with $1176$ variables and $3813768$ clauses. We could try to improve general SAT solvers to the point where they can handle this, rather than using a pure brute force approach or anything specific to Ramsey numbers.
Recently a SAT solver was used on the Erdős discrepancy problem, which naively had 1161 variables, though I think their encoding used somewhat more variables than that. I have no idea what the computational complexity of using this sort of algorithm on the problem is. I'm sure it would be much more efficient than brute force, though.
A: Several years ago I found a method based on continuous optimizaton which can sometimes
find lower bound. It also applies to the SAT problem but it may not be exactly the same as the SAT solver method.
Given the number of vertices $n$, and positive
integers $k,l$, we can code all $2$-colorings of the edges of $K_n$
by (the upper triangular part of) a binary matrix $x_{ij}, 1\le i <
j \le n$, and write down the energy function
$$\phi_{kl}^{(n)}(x)= \sum_{1 \le i_1 <...<i_k \le n} \prod_{1 \le s<
t \le k} x_{i_s i_t} + \sum_{1 \le j_1<...<j_l \le n} \prod_{1 \le s
< t \le l}(1- x_{j_s j_t}),$$
which counts the total number of monochromatic $1$-$K_k$ or
$0$-$K_l$. We now interpolate and think of $\phi(x)$ as a polynomial
function of the ${ n \choose 2}$ real variables $x_{ij}$ which is
linear in each, and must therefore satisfies a strong mean-value
property :
Lemma. Let $f(x_1,...,x_n)$ be a real function which is linear in
each variable. Then for any axes-parallel rectangular box of any
dimension $k$, the value of $f$ at the center is the average value of
$f$ over the vertices of the box.
Proof. This is true for $k=1$ (i.e. for a line), since $f$ is linear. For a $k$-dimensional box, we just have to take the average over the straight line joining the centers of two opposite $k-1$-dimensional faces which equals the
average over the whole box.
Applying this to $\phi$, we see that if
$$\phi^{(n)}_{kl}(1/2,...,1/2)={ n \choose k }  2^{-{k \choose 2}}
+{n \choose l} 2^{-{l \choose 2}}<1,$$
we get a lower bound $R(k,l)>n$, which is the same bound as the original probabilistic counting method. We now observe that we can make the same conclusion
if we can find any $x$ inside the unit box $[0,1]^{n \choose 2}$,
with $\phi(x)<1$ because of the maximum principle: $\phi$ is
harmonic in any subset of the variables so any extremal value of
$\phi$ inside the box  must already occur at some vertex. So instead
of doing brute force searching over the vertices discretely, we can
try to minimize $\phi$ over the whole box continuously by some form
of gradient descent algorithm.
Finding the minimum of a polynomial inside a box is however an NP-hard problem since the energy function which counts the number of
falsified clauses of a truth assignment of a boolean formula in
conjunctive normal form has exactly the same sum-product form as
$\phi$ and SAT is NP-complete.
Evaluating $\phi$ and its gradient is compute intensive but is
polynomial in $n$ for fixed $k$ and $l$ and is certainly doable for
the range of $R(5,5)$ up to $n=49$.
Maybe someone with more computing power and better optimization
algorithm can try this. The idea is that we don't look at all the
vertices just the good ones following the gradient. The problem is
of course that we cannot be sure the best we have found is the true minimum
unless it is of zero energy.
(Added 28 Feb 23)

*

*Evaluating $\phi$ at $x=(1/2)^m, m=\binom{n}2$ gives the same bound as the original probabilistic existence method. However our method is constructive. One can always change each $x_{ij}=1/2$ to either $0$ or $1$ without increasing $\phi$ since $\phi$ is linear in each variable. In $m$ steps we will arrive at a vertex $x_0$ with $\phi(x_0) \le \phi(x)<1$ and hence must be zero since $\phi$ is non-negative integral at the verticesr. So $x_0$ defines an extremal graph with no monochromatic. The same method works for 2-colorings of hypergraphs.


*The average bound is very weak. If we choose $n$ to be just below a known lower bound,where $\phi((1/2)^m)$ may be huge, we may still have $\phi(x_0)=0$. In this way we have a method to compute rather good lower bound.


*The method is generic since it applies to SAT. For any problem $\pi \in NP$, the process of writing down a similar $\phi_\pi$ is equivalent to doing a reduction from $\pi $ to SAT, which is always possible by the fundamental Cook-Levin theorem (ie. SAT is NP-complete). One can think of Cook-Levin theorem as coding a program to reduce a generic $\pi \in NP$ to SAT in the low level language of Turing machine. To find $\phi_\pi(x)$ is the same as coding this reduction for a particular $\pi$
in the high level language called polynomial.


*In this way we have essentially a generic algorithm for finding rather good algorithm for all problem in NP. Our initial hope to always find the optimal solution does not materialize since it would implies $P=NP$ which is most likely false.


*It is known $43 \le R(5,5) \le 48$. If $P=NP$, we would be able to compute $Min_{[0,1]^{\binom{43}2}} \phi^{43}_{5,5}(x)$ to conclude either $R(5,5)=43$ or $R(5,5)>43$ and in the later case we move on to $n=44$. $R(5,5),R(6,6)...$ would be determined.


*It is not surprising we relate Ramsey number to complexity. Ramsey theory grew out of a lemma of his in paper where he use it to give a algorithm a restricted decision problem for first order logic.
A: I like intelligent brute force algorithms.  While there may be more clever ones, the following
is pretty simple.  I will specialize it to the case of looking for $R(6,6)$.
Suppose we have a list (or way of streaming) all the colorings of the edges of $K_n$ which
do not induce a blue $K_6$ or a red $K_6$. (So if $n$ were $6$, this would be $2$ less than $2^{15}$.)
Load up a coloring, and construct a new point connected to the $n$ points.  One can
employ some smarts in deciding which of the $2^n$ colorings will produce colorings of
$K_{n+1}$ which avoid a monchromatic $K_6$.  If one is really on the ball, one can toss out
colorings which are isomorphic to a coloring already produced.
Once one has generated a comprehensive and nonempty list for $K_{n+1}$, then one
can move to $K_{n+2}$.   A problem with this is space: when $n$ reaches $20$, the bulk of
the colorings will be isomorphic to $20!$ (greater than $10^{17}$) others, and it will require
some ingenuity and more time to pick one representative of each isomorphism class.
Even when you have such, it is likely that you will have over $2^{50}$ valid colorings to
test.  You might say that's not too far from $10^{15}$, surely that can be done within a year.
Maybe, but n=20 is just the beginning.  Even if $R(6,6)$ turned out to be $30$ (a serious
underestimate), getting to there will take repeating the process to get to $20$ at least
another $2^{50}$ times.  Using this algorithm, we may have to worry about heat-death of
the universe occurring before we finish.
A: I'm not sure we could find $R(5,5)$ in one year, because exhaustive search is infeasible and one year is probably not enough time to develop the extra theory that would make it possible.
I'll dispose of one type of exhaustive search, similar to what Masked Avenger proposes.  Suppose we generate all graphs with no 5-clique or 5-independent-set by adding one vertex at a time with complete isomorph rejection. Suppose each computer could make one graph per microsecond (better than at present) and we have one billion computers working in parallel.  Then we would know $R(5,5)$ in something like $10^{60}$ years. This is an actual estimate, not a guess.
There are ways to constrain the search to a fraction of all graphs, and also other ways to organize the search, but I don't see any that offers a promise of feasibility.
I'm dubious about SAT-solvers doing much better, since the problem is one that has a vast number of near-solutions.  That is, one can assign a vast number of values to, say, 90% of the variables (probably: any 90% of the variables) and still all the incomplete constraints will appear feasible.
The only real chance is a theoretical breakthrough.  If we got all the world's mathematicians onto the problem, the odds aren't bad I think.
