Fractional Chromatic Numbers from Exact Decision Diagrams
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909377922859008 |
|---|---|
| author | Brand, Timo Held, Stephan |
| author_facet | Brand, Timo Held, Stephan |
| contents | Recently, Van Hoeve proposed an algorithm for graph coloring based on an integer flow formulation on decision diagrams for stable sets. We prove that the solution to the linear flow relaxation on exact decision diagrams determines the fractional chromatic number of a graph. This settles the question whether the decision diagram formulation or the fractional chromatic number establishes a stronger lower bound. It also establishes that the integrality gap of the linear programming relaxation is O(log n), where n represents the number of vertices in the graph. We also conduct experiments using exact decision diagrams and could determine the chromatic number of r1000.1c from the DIMACS benchmark set. It was previously unknown and is one of the few newly solved DIMACS instances in the last 10 years. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_03003 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Fractional Chromatic Numbers from Exact Decision Diagrams Brand, Timo Held, Stephan Combinatorics Discrete Mathematics 05C15 G.2.2 Recently, Van Hoeve proposed an algorithm for graph coloring based on an integer flow formulation on decision diagrams for stable sets. We prove that the solution to the linear flow relaxation on exact decision diagrams determines the fractional chromatic number of a graph. This settles the question whether the decision diagram formulation or the fractional chromatic number establishes a stronger lower bound. It also establishes that the integrality gap of the linear programming relaxation is O(log n), where n represents the number of vertices in the graph. We also conduct experiments using exact decision diagrams and could determine the chromatic number of r1000.1c from the DIMACS benchmark set. It was previously unknown and is one of the few newly solved DIMACS instances in the last 10 years. |
| title | Fractional Chromatic Numbers from Exact Decision Diagrams |
| topic | Combinatorics Discrete Mathematics 05C15 G.2.2 |
| url | https://arxiv.org/abs/2411.03003 |