Graph colouring on DIMACS, open instances

# Graph colouring on DIMACS, open instances ## Goal Vertex colouring: give every vertex a colour so that no edge joins two vertices of the same colour, using as few colours as possible. The graphs are ten instances from the DIMACS colouring challenge whose chromatic number is still unknown: the best lower bound (a clique, or the fractional chromatic number computed by column generation) is strictly below the fewest colours anyone has managed. Random graphs `DSJCn.d` (Johnson et al. 1991, `n` vertices, edge density `d`), the flat graph `flat1000_76_0` (Culberson: 1000 vertices partitioned into 76 classes with edges only between classes, so a 76-colouring exists by construction, yet the best colouring found has 81 colours), `latin_square_10` (Lewandowski and Condon; a 10 x 10 Latin square completion graph with 900 vertices) and `C2000.5` (Trick's 2000-vertex random graph at density 0.5). `colour.py` exposes colour(name: str, n: int, edges: list[tuple[int, int]], time_budget: float, seed: int) -> list[int] `edges` is a list of `(u, v)` with `0 <= u < v < n` (each edge once); `name` is the instance label. Return a list of `n` non-negative integers, the colour of each vertex. Colours need not be contiguous; the eval counts distinct values after checking that every edge is properly coloured, so nothing the solver reports is trusted. Instance files live in `instances/<name>.txt` (line 1 `n m`, then the upper triangle of the adjacency matrix as zlib-compressed, base64-encoded bits); they are not mutable and the eval decodes them itself. ## Metric metric = mean over the 10 instances of best_known(name) / colours(name) A ratio of 1.0 matches the best-known colouring; above 1.0 beats it, and the eval lists those instances in `records_beaten`. An improper colouring, a wrong-length list or a non-integer colour on any instance is a failed run, as is exceeding the time budget. Environment knobs the eval honours: - `ZT_EVAL_SEED`: only seeds the `seed` handed to your solver. The instance set is fixed. - `ZT_EVAL_PER_INSTANCE_SECONDS`: the `time_budget` per instance (default 8; the full run takes about 75 s, the rest being the eval's own decoding and checking of the dense graphs). - `ZT_EVAL_INSTANCES`: comma-separated subset of the names below, for quick local runs (`ZT_EVAL_INSTANCES=DSJC250.5,DSJC500.1 python eval.py`). ## Records Best-known upper bounds (fewest colours in a legal colouring reported in the literature) from Goudet, Grelier and Hao 2022 ("A deep learning guided memetic framework for graph coloring problems", Table 7, arXiv:2109.05948) and Moalic and Gondran 2018 (HEAD, Journal of Heuristics 24). Lower bounds are the safe fractional-chromatic-number bounds of Held, Cook and Sewell 2012 (Mathematical Programming Computation 4, Table 2; the branch-and-price bound for DSJC1000.9 is their Table 3), except DSJC500.9 where CPLEX pushed the bound to 124 in 2024 (numerically unsafe, arXiv:2411.03003). Every row has lower bound < upper bound; r1000.1c (98) is left out because that same 2024 paper computed its chromatic number, and le450_25c/d, flat1000_50_0/60_0, DSJR500.1c/5, r1000.5 are left out because they are closed. | instance | n | m | best-known colours | found by | lower bound | optimal? | |---|---|---|---|---|---|---| | DSJC250.5 | 250 | 15668 | 28 | Galinier and Hao 1999 and many since | 26 | no | | DSJC500.1 | 500 | 12458 | 12 | many (tabu search, HEA, MMT, ...) | 5 (clique; fractional bound unfinished) | no | | DSJC500.5 | 500 | 62624 | 47 | Titiloye and Crispin 2011 (QA-col), HEAD 2018 | 43 | no | | DSJC500.9 | 500 | 112437 | 126 | Galinier and Hao 1999 and many since | 124 | no | | DSJC1000.1 | 1000 | 49629 | 20 | Galinier and Hao 1999 and many since | 6 (clique; fractional bound unfinished) | no | | DSJC1000.5 | 1000 | 249826 | 82 | Titiloye and Crispin 2012, HEAD 2018 | 73 | no | | DSJC1000.9 | 1000 | 449449 | 222 | Titiloye and Crispin 2011, HEAD 2018 | 216 | no | | flat1000_76_0 | 1000 | 246708 | 81 | Titiloye and Crispin 2012, HEAD 2018 | 72 (a planted 76-colouring exists) | no | | latin_square_10 | 900 | 307350 | 97 | Titiloye and Crispin 2011 (distributed hybrid QA) | 90 | no | | C2000.5 | 2000 | 999836 | 145 | Titiloye and Crispin 2012, HEAD 2018 | 16 | no | The 47 on DSJC500.5, the 82 on DSJC1000.5 and the 81 on flat1000_76_0 are reached by only two or three published algorithms after hours of CPU time; 48, 83 and 82 are the practical targets on a short budget, and 1.0 on the small graphs. Anything above 1.0 is a record candidate. ## Constraints - Standard library only. No numpy, no scipy. The eval rejects other imports. - Respect `time_budget` (seconds, per call). The eval fails a call that runs more than 25 % over. - Deterministic given `seed`: use `random.Random(seed)`. - `edges` is a copy; the eval scores against its own. ## Ideas that are known to matter (check the journal before repeating one) - Work on the k-colouring decision problem: fix `k`, minimise the number of conflicting edges, and decrease `k` whenever you reach zero. Every record above was set this way, never by a constructive heuristic. Always keep the last legal colouring to return. - TabuCol (Hertz and de Werra 1987; Galinier and Hao 1999 tuning): one-move neighbourhood (recolour a conflicting vertex), a `gamma[v][c]` matrix of neighbour colour counts for `O(1)` move evaluation, tabu tenure `0.6 * conflicts + random(0, 9)`, aspiration when a move beats the best conflict count. The baseline is a plain TabuCol; making its inner loop fast (only scan conflicting vertices, keep the best move incrementally) is the first thing to do. - Hybrid evolutionary algorithm (Galinier and Hao 1999; HEAD, Moalic and Gondran 2018): a population of two to ten k-colourings, greedy partition crossover (build the child class by class, taking the largest remaining class from alternating parents), TabuCol on the child. HEAD with a population of two plus two elite solutions is what found 47 on DSJC500.5 and 82 on DSJC1000.5. - Partial colouring / partialcol (Blochliger and Zufferey 2008): keep a proper partial colouring and minimise the number of uncoloured vertices instead of conflicts; better on the sparse DSJC*.1 graphs. - Quantum annealing (Titiloye and Crispin 2011, 2012) is a population of TabuCol-like walkers coupled by a penalty on their pairwise distance; it holds most of the dense-graph records. - Independent-set extraction (Hertz, Plumettaz, Zufferey; MMT 2008): on the dense graphs (DSJC1000.9, C2000.5, latin_square_10) repeatedly remove a large independent set found by tabu search, then colour the residual graph. Reduces the problem the local search has to solve. - Colour-class counting is what the eval scores: after a legal k-colouring, try to empty the smallest class by moving its vertices into the others (a Kempe-chain or tabu step) before giving up on `k - 1`. Write one honest line in `NOTES.md`: the idea, and which instances it helped. Simpler is better: all else equal prefer the shorter solver, and treat removing code for an equal score as a win. Log every experiment, including discards, in your results.tsv.