Message passing for the coloring problem: Gallager meets Alon and Kahale

zbMATH Open1192.68943arXiv0710.3928MaRDI QIDQ3576765FDOQ3576765

Authors: Sonny Ben-Shimon, Dan Vilenchik 

Publication date: 2 August 2010

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.

Full work available at URL: https://arxiv.org/abs/0710.3928

Recommendations

• A Simple Message Passing Algorithm for Graph Partitioning Problems
• Complete convergence of message passing algorithms for some satisfiability problems
• Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems
• scientific article; zbMATH DE number 5041476
• Patterns from nature: distributed greedy colouring with simple messages and minimal graph knowledge
• On the Complexity of Distributed Greedy Coloring
• Message-Passing Algorithms: Reparameterizations and Splittings
• scientific article; zbMATH DE number 7651156

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computer aspects of numerical algorithms (65Y99)

Cited In (1)

• A spectral approach to analysing belief propagation for 3-colouring

This page was built for publication: Message passing for the coloring problem: Gallager meets Alon and Kahale

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3576765)