Summary of Sat Encoding Of Partial Ordering Models For Graph Coloring Problems, by Daniel Faber and Adalat Jabrayilov and Petra Mutzel
SAT Encoding of Partial Ordering Models for Graph Coloring Problems
by Daniel Faber, Adalat Jabrayilov, Petra Mutzel
First submitted to arxiv on: 23 Mar 2024
Categories
- Main: Artificial Intelligence (cs.AI)
- Secondary: Discrete Mathematics (cs.DM); Data Structures and Algorithms (cs.DS); Logic in Computer Science (cs.LO)
GrooveSquid.com Paper Summaries
GrooveSquid.com’s goal is to make artificial intelligence research accessible by summarizing AI papers in simpler terms. Each summary below covers the same AI paper, written at different levels of difficulty. The medium difficulty and low difficulty versions are original summaries written by GrooveSquid.com, while the high difficulty version is the paper’s original abstract. Feel free to learn from the version that suits you best!
| Summary difficulty | Written by | Summary |
|---|---|---|
| High | Paper authors | High Difficulty Summary Read the original abstract here |
| Medium | GrooveSquid.com (original content) | Medium Difficulty Summary A novel SAT encoding is proposed for two combinatorial optimization problems: graph coloring and bandwidth coloring. The graph coloring problem seeks to minimize the number of colors required to assign to vertices in a graph, while ensuring adjacent vertices receive distinct colors. Bandwidth coloring generalizes this by incorporating edge weights that enforce a minimal “distance” between assigned colors, with the goal of minimizing the largest color used. Experimental results show that the new encoding outperforms state-of-the-art approaches on sparse graphs and certain DIMACS instances for graph coloring. Theoretical analysis demonstrates that partial-ordering based SAT and ILP formulations have smaller sizes than assignment-based models for bandwidth coloring. Practical evaluation confirms dominance over existing encodings, including those of the graph coloring problem. |
| Low | GrooveSquid.com (original content) | Low Difficulty Summary This paper finds new ways to solve two complex problems: graph coloring and bandwidth coloring. Graph coloring is like color-coding a map so that neighboring countries have different colors. Bandwidth coloring adds an extra level of difficulty by considering how far apart colors should be. The researchers created new methods for solving these problems using something called SAT encoding. They tested their methods on real-life examples and found they worked better than existing approaches. This is important because it can help us solve other complex problems in the future. |
Keywords
* Artificial intelligence * Optimization
