Paper Info
Title
Message passing for the coloring problem: Gallager meets Alon and Kahale
Abstract
Message passing algorithms are popular in many combinatorial optimization problems. For example, experimental results show that {\em survey propagation} (a certain message passing algorithm) is effective in finding proper $k$-colorings of random graphs in the near-threshold regime. In 1962 Gallager introduced the concept of Low Density Parity Check (LDPC) codes, and suggested a simple decoding algorithm based on message passing. In 1994 Alon and Kahale exhibited a coloring algorithm and proved its usefulness for finding a $k$-coloring of graphs drawn from a certain planted-solution distribution over $k$-colorable graphs. In this work we show an interpretation of Alon and Kahale's coloring algorithm in light of Gallager's decoding algorithm, thus showing a connection between the two problems - coloring and decoding. This also provides a rigorous evidence for the usefulness of the message passing paradigm for the graph coloring problem. Our techniques can be applied to several other combinatorial optimization problems and networking-related issues.
Year
Venue
Keywords
2007
Discrete Mathematics & Theoretical Computer Science
graph coloring problem,message passing,ldpc code,discrete mathematics,random graph,low density parity check
Field
DocType
Volume
Discrete mathematics,Edge coloring,Combinatorics,Random graph,Low-density parity-check code,Decoding methods,Greedy coloring,Mathematics,Message passing,Graph coloring,Coloring problem
Journal
abs/0710.3928
Issue
ISSN
Citations 
1
DMTCS Proceedings of the 13th Annual Conference on Analysis of Algorithms (AofA'07), Juan-les-pins, France, 2007. pp. 217--226.
1
PageRank 
References 
Authors
0.36
17
2
Name
Order
Citations
PageRank
Sonny Ben-Shimon1494.63
Dan Vilenchik214313.36