One Color Preprocessing Improves DSATUR

单色预处理改进 DSATUR 算法

The Graph Coloring Problem (GCP) is NP-hard and DSATUR stands as one of the fastest heuristics for it despite producing colorings that typically use more colors than state-of-the-art coloring algorithms. 图着色问题（GCP）是一个 NP-hard 问题。尽管 DSATUR 算法产生的着色方案通常比最先进的着色算法使用更多的颜色，但它仍然是该问题最快的启发式算法之一。

We propose SSLD (Semidefinite Spectral Learning with DSATUR), which improves DSATUR by preprocessing a first good color class before letting DSATUR complete coloring the rest of the given graph. 我们提出了 SSLD（基于 DSATUR 的半定谱学习算法），该算法通过预处理出一个高质量的首个颜色类，随后再由 DSATUR 完成给定图的剩余着色工作，从而改进了 DSATUR。

We obtain this color class from a Semidefinite Programming (SDP), similar to an SDP used to compute the Lovász theta number. To the best of our knowledge, SSLD is the first approach to improve DSATUR by preprocessing through fixed color classes. 我们通过半定规划（SDP）获得该颜色类，其方法类似于计算 Lovász theta 数所使用的 SDP。据我们所知，SSLD 是首个通过固定颜色类预处理来改进 DSATUR 的方法。

We evaluate SSLD against DSATUR and against a naive 1-color-class preprocessing algorithm on DIMACS instances, random graphs (Erdős—Rényi, Watts-Strogatz, Barabási—Albert), Frequency Assignment and Job Shop Scheduling instances. 我们在 DIMACS 实例、随机图（Erdős—Rényi、Watts-Strogatz、Barabási—Albert）、频率分配和作业车间调度实例上，将 SSLD 与 DSATUR 以及一种朴素的单颜色类预处理算法进行了对比评估。

SSLD matches or beats DSATUR in almost every case across over 1600 benchmark instances, and out performs the naive GISD baseline, allows us to confirm the value brought by the SDP-guided choice of the first color class. 在超过 1600 个基准测试实例中，SSLD 在几乎所有情况下都达到或超过了 DSATUR 的表现，并优于朴素的 GISD 基准，这证实了由 SDP 引导选择首个颜色类所带来的价值。

This quality comes at a runtime cost of roughly 195 times slower that DSATUR, but demonstrating that SDP-guided preprocessing of a first color class is a direction for future improvements. 这种质量提升是以大约 195 倍于 DSATUR 的运行时间成本为代价的，但这证明了通过 SDP 引导预处理首个颜色类是未来改进的一个方向。