Computer Science – Discrete Mathematics
Scientific paper
2009-09-28
Computer Science
Discrete Mathematics
Scientific paper
In this paper we propose a deterministic algorithm for approximately counting the k-colourings of sparse random graphs G(n,d/n), (each edge is chosen independently with probability d/n and d is fixed). In particular, our algorithm computes in polynomial time a (1\pm n^(-Omega(1)))$-approximation of the logarithm of the number of k-colourings of $G(n,d/n)$ for k\geq 2.1 d$ with high probability. Our algorithm is related to the algorithms of A. Bandyopadhyay et al. in SODA '06, and A. Montanari et al. in SODA '06, i.e. it uses correlation decay to compute deterministically marginals of Gibbs distribution. However, we use correlation decay properties of the Gibbs distribution in a completely different manner, i.e. given the graph G(n,d/n), we alter the graph structure in some specific region L subset of V (by deleting edges between vertices of L) and then we show that the effect of this change on the marginals of Gibbs distribution, diminishes as we move away from L. Our approach is novel and suggests a new context for the study of deterministic counting algorithms.
No associations
LandOfFree
Deterministic counting of graph colourings using sequences of subgraphs 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 Deterministic counting of graph colourings using sequences of subgraphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Deterministic counting of graph colourings using sequences of subgraphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-664317