一种颜色预处理可提高 DSATUR

arXiv:2609.17633v1 公告类型：新 摘要：图着色问题 (GCP) 是 NP 难题，尽管 DSATUR 生成的着色通常使用比最先进的着色算法更多的颜色，但它是最快的启发式算法之一。我们提出 SSLD（使用 DSATUR 的半定谱学习），它通过在让 DSATUR 完成给定图的其余部分的着色之前预处理第一个好的颜色类来改进 DSATUR。我们通过半定规划 (SDP) 获得此颜色类别，类似于用于计算 Lov\'asz theta 数的 SDP。据我们所知，SSLD 是第一个通过固定颜色类别进行预处理来提高 DSATUR 的方法。我们针对 DSATUR 以及 DIMACS 实例、随机图（Erd\H{o}s--R\'enyi、Watts-Strogatz、Barab\'asi--Albert）、频率分配和作业车间调度实例上的朴素 1 色类预处理算法来评估 SSLD。 SSLD 在 1600 多个基准实例中的几乎所有情况下都匹配或击败 DSATUR，并且优于朴素的 GISD 基线，使我们能够确认 SDP 引导的第一颜色类别选择所带来的价值。这种质量的运行时间成本大约比 DSATUR 慢 195 倍，但表明 SDP 引导的第一颜色类预处理是未来改进的方向。