Sonny Ben-Shimon ; Dan Vilenchik
-
Message passing for the coloring problem: Gallager meets Alon and Kahale
dmtcs:3546 -
Discrete Mathematics & Theoretical Computer Science,
January 1, 2007,
DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07)
-
https://doi.org/10.46298/dmtcs.3546
Message passing for the coloring problem: Gallager meets Alon and Kahale
Authors: Sonny Ben-Shimon 1; Dan Vilenchik 1
NULL##NULL
Sonny Ben-Shimon;Dan Vilenchik
1 Blavatnik School of Computer Science [Tel Aviv]
Message passing algorithms are popular in many combinatorial optimization problems. For example, experimental results show that \emphsurvey 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.