How Much Backtracking Does It Take to Color Random Graphs? Rigorous Results on Heavy Tails

摘要

For many backtracking search algorithms, the running time has been found experimentally to have a heavy-tailed distribution, in which it is often much greater than its median. We analyze two natural variants of the Davis-Putnam-Logemann-Loveland (DPLL) algorithm for Graph 3-Coloring on sparse random graphs of average degree c. Let P_c(b) be the probability that DPLL backtracks 6 times. First, we calculate analytically the probability P_c(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" regime 1 < c < c~* where P_c(0) > 0 — including just above the degree c = 1 where the giant component first appears — the expected number of backtrackings 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.