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

MaRDI QIDQ3576765zbMATH OpenFDO

Authors Sonny Ben-Shimon, Dan Vilenchik

Publication date 2 August 2010

Full work available at URL https://arxiv.org/abs/0710.3928, https://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/view/dmAH0115/0.html

Mathematics Subject Classification ID

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

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.

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

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)