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

Simple item page
dc.creatorJia, Haixia
dc.creatormoore, Cristopher
dc.date2004-12-17
dc.date.accessioned2026-07-07T03:02:46Z
dc.date.available2026-07-07T03:02:46Z
dc.descriptionMany 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 P_c(b) be the probability that DPLL backtracks b 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 \to c^* = 3.847... Then we show that even in the ``easy'' phase 1 < c < c^* where P_c(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 P_c(b) ~ b^{-1} up to an exponential cutoff.
dc.descriptionlong version of paper in CP 2004
dc.identifierhttps://arxiv.org/abs/cond-mat/0412489
dc.identifierhttp://arxiv.org/abs/cond-mat/0412489
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/25516
dc.subjectDisordered Systems and Neural Networks
dc.subjectStatistical Mechanics
dc.titleHow much backtracking does it take to color random graphs? Rigorous results on heavy tails
dc.typetext

Files

Collections

arXiv