The Graph Coloring Problem (GCP) is NP‑hard and DSATUR remains one of the fastest heuristics, yet it typically uses more colors than state‑of‑the‑art algorithms. We introduce SSLD (Semidefinite Spectral Learning with DSATUR), which improves DSATUR by preprocessing a high‑quality first color class before DSATUR colors the remaining vertices. This class is obtained from a semidefinite program (SDP) similar to the SDP used for computing the Lovász theta number.
To the best of our knowledge, SSLD is the first approach that enhances DSATUR via fixed‑color‑class preprocessing. We evaluate it on DIMACS benchmarks, random graphs (Erdős‑Rényi, Watts‑Strogatz, Barabási‑Albert), frequency‑assignment, and job‑shop scheduling instances.
Results show that SSLD matches or beats DSATUR on more than 1600 benchmark instances and outperforms the naive 1‑color‑class baseline (GISD), confirming the benefit of the SDP‑guided first color class. The improvement comes at a runtime cost of roughly 195× slower than DSATUR, demonstrating that SDP‑guided preprocessing is a promising direction for future work.
Review