How much backtracking does it take to color random graphs? Rigorous results on heavy tails

Original · EN

Many backtracking algorithms exhibit heavy-tailed distributions, in which their running time is often much longer than their median. We analyze the behavior of two natural variants of the Davis-Putnam-Logemann-Loveland (DPLL) algorithm for Graph 3-Coloring on sparse random graphs G(n,p=c/n). Let Pc(b) be the probability that DPLL backtracks b times. First, we calculate analytically the probability Pc(0) that these algorithms find a 3-coloring with no backtracking at all, and show that it goes to zero faster than any analytic function as c → c* = 3.847... Then we show that even in the ``easy'' phase 1 < c < c* where Pc(0) > 0, including just above the emergence of the giant component, the expected number of backtracks is exponentially large with positive probability. To our knowledge this is the first rigorous proof that the running time of a natural backtracking algorithm has a heavy tail for graph coloring. Moreover, our results show that these algorithms take exponential time, not just below the 3-colorability threshold, but just above the degree c=1 at which the giant component first appears. In addition, we give experimental evidence and heuristic arguments that this tail takes the form Pc(b) b⁻¹ up to an exponential cutoff.