Message passing for the coloring problem: Gallager meets Alon and Kahale
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 int...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2007-01-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/3546/pdf |
| _version_ | 1797270413152092160 |
|---|---|
| author | Sonny Ben-Shimon Dan Vilenchik |
| author_facet | Sonny Ben-Shimon Dan Vilenchik |
| author_sort | Sonny Ben-Shimon |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T02:03:52Z |
| format | Article |
| id | doaj.art-4f50ef7483954590bc150e9dc5d6029f |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T02:03:52Z |
| publishDate | 2007-01-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-4f50ef7483954590bc150e9dc5d6029f2024-03-07T14:34:52ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502007-01-01DMTCS Proceedings vol. AH,...Proceedings10.46298/dmtcs.35463546Message passing for the coloring problem: Gallager meets Alon and KahaleSonny Ben-Shimon0Dan Vilenchik1Blavatnik School of Computer Science [Tel Aviv]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.https://dmtcs.episciences.org/3546/pdfgraph coloringmessage passinglow density parity check code[info.info-ds] computer science [cs]/data structures and algorithms [cs.ds][info.info-dm] computer science [cs]/discrete mathematics [cs.dm][math.math-co] mathematics [math]/combinatorics [math.co][info.info-cg] computer science [cs]/computational geometry [cs.cg] |
| spellingShingle | Sonny Ben-Shimon Dan Vilenchik Message passing for the coloring problem: Gallager meets Alon and Kahale Discrete Mathematics & Theoretical Computer Science graph coloring message passing low density parity check code [info.info-ds] computer science [cs]/data structures and algorithms [cs.ds] [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] [math.math-co] mathematics [math]/combinatorics [math.co] [info.info-cg] computer science [cs]/computational geometry [cs.cg] |
| title | Message passing for the coloring problem: Gallager meets Alon and Kahale |
| title_full | Message passing for the coloring problem: Gallager meets Alon and Kahale |
| title_fullStr | Message passing for the coloring problem: Gallager meets Alon and Kahale |
| title_full_unstemmed | Message passing for the coloring problem: Gallager meets Alon and Kahale |
| title_short | Message passing for the coloring problem: Gallager meets Alon and Kahale |
| title_sort | message passing for the coloring problem gallager meets alon and kahale |
| topic | graph coloring message passing low density parity check code [info.info-ds] computer science [cs]/data structures and algorithms [cs.ds] [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] [math.math-co] mathematics [math]/combinatorics [math.co] [info.info-cg] computer science [cs]/computational geometry [cs.cg] |
| url | https://dmtcs.episciences.org/3546/pdf |
| work_keys_str_mv | AT sonnybenshimon messagepassingforthecoloringproblemgallagermeetsalonandkahale AT danvilenchik messagepassingforthecoloringproblemgallagermeetsalonandkahale |