Average-case complexity of backtrack search for coloring sparse random graphs

Mann, Zoltán Ádám and Szajkó, Anikó (2013) Average-case complexity of backtrack search for coloring sparse random graphs. Journal of Computer and System Sciences, 79 (8). pp. 1287-1301. ISSN 0022-0000

Preview

Text Mann_Szajko_JCSS_2013.pdf Download (383kB) | Preview

Abstract

We investigate asymptotically the expected number of steps taken by backtrack search for $k$-coloring random graphs $G_{n,p(n)}$ or proving non-$k$-colorability, where $p(n)$ is an arbitrary sequence tending to 0, and $k$ is constant. Contrary to the case of constant $p$, where the expected runtime is known to be $O(1)$, we prove that here the expected runtime tends to infinity. We establish how the asymptotic behaviour of the expected number of steps depends on the sequence $p(n)$. In particular, for $p(n)=d/n$, where $d$ is a constant, the runtime is always exponential, but it can be also polynomial if $p(n)$ decreases sufficiently slowly, e.g. for $p(n)=1/\ln n$.

Actions (login required)

Edit Item