SSLD
A graph coloring heuristic that improves upon DSATUR by preprocessing monochromatic classes using semidefinite programming (SDP). It leverages the spectral geometry of the Lovász theta number to select high-quality initial color classes and is the first method to improve DSATUR through fixed-class preprocessing.
Timeline (last 90 days)
SSLD (Semidefinite Spectral Learning with DSATUR) is a new method proposed in a paper posted on arXiv (arXiv:2609.17633) that pre-seeds a high-quality first color class using semidefinite programming before DSATUR begins, and then hands off the remaining vertex coloring to DSATUR.
The semidefinite program used by SSLD to find the first color class is similar to the semidefinite program used to compute the Lovász theta number.
The authors state that, to their knowledge, SSLD is the first method to improve DSATUR by preprocessing with a fixed color class.
SSLD was benchmarked on more than 1,600 benchmark instances, covering the DIMACS test set, three random graph models (Erdős–Rényi, Watts–Strogatz, and Barabási–Albert), as well as frequency assignment and job-shop scheduling instances.
SSLD matches or surpasses DSATUR's coloring quality in nearly all settings, while also clearly outperforming the naive GISD baseline (single color-class preprocessing without SDP guidance).
SSLD's running time is approximately 195 times that of DSATUR.
If coloring quality is a hard constraint and computation time is relatively flexible, SSLD is worth using; if maximum speed is the priority, the original DSATUR is the more pragmatic choice.
SSLD embodies the idea of combining continuous optimization (SDP/spectral methods) with discrete heuristics: using SDP to capture the global graph structure, then using DSATUR for fast local decisions.
The authors position SSLD as a directional proof of concept rather than a ready-to-use tool, viewing SDP-guided first color-class preprocessing as an improvement path worth further exploration.
All Facts (9)
The authors position SSLD as a directional proof of concept rather than a ready-to-use tool, viewing SDP-guided first color-class preprocessing as an improvement path worth further exploration.
50%UnverifiedThe semidefinite program used by SSLD to find the first color class is similar to the semidefinite program used to compute the Lovász theta number.
50%UnverifiedThe authors state that, to their knowledge, SSLD is the first method to improve DSATUR by preprocessing with a fixed color class.
50%UnverifiedSSLD was benchmarked on more than 1,600 benchmark instances, covering the DIMACS test set, three random graph models (Erdős–Rényi, Watts–Strogatz, and Barabási–Albert), as well as frequency assignment and job-shop scheduling instances.
50%UnverifiedSSLD matches or surpasses DSATUR's coloring quality in nearly all settings, while also clearly outperforming the naive GISD baseline (single color-class preprocessing without SDP guidance).
50%UnverifiedSSLD's running time is approximately 195 times that of DSATUR.
50%UnverifiedIf coloring quality is a hard constraint and computation time is relatively flexible, SSLD is worth using; if maximum speed is the priority, the original DSATUR is the more pragmatic choice.
50%UnverifiedSSLD embodies the idea of combining continuous optimization (SDP/spectral methods) with discrete heuristics: using SDP to capture the global graph structure, then using DSATUR for fast local decisions.
50%UnverifiedSSLD (Semidefinite Spectral Learning with DSATUR) is a new method proposed in a paper posted on arXiv (arXiv:2609.17633) that pre-seeds a high-quality first color class using semidefinite programming before DSATUR begins, and then hands off the remaining vertex coloring to DSATUR.
50%