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

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

2004-12-17

arxiv.org/abs/cond-mat/0412489v1

Physics

Condensed Matter

Disordered Systems and Neural Networks

long version of paper in CP 2004

Scientific paper

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 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.

Affiliated with

Also associated with

No associations

Rating

How much backtracking does it take to color random graphs? Rigorous results on heavy tails does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with How much backtracking does it take to color random graphs? Rigorous results on heavy tails, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and How much backtracking does it take to color random graphs? Rigorous results on heavy tails will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-159117