论文标题
最大$ k $ - 可油的子图问题和相关问题
The maximum $k$-colorable subgraph problem and related problems
论文作者
论文摘要
最大$ k $ - 可加油子图（m $ k $ cs）问题是在给定图中找到具有最大基数的诱导$ k $可加油子图。本文是对M $ K $ CS问题的深入分析，该分析考虑了各种半决赛编程放松，包括其理论和数值比较。为了简化这些放松，我们利用置换颜色引起的对称性以及适用时给定图的对称性。我们还展示了如何在子集的排列下利用不变性来解决其他分区问题，以及如何使用M $ K $ CS问题来得出图形的色数上的界限。 我们的数值结果验证了所提出的放松为M $ K $ CS问题提供了强大的界限，并且对于大多数测试实例，这些放松的界限优于现有界限。
The maximum $k$-colorable subgraph (M$k$CS) problem is to find an induced $k$-colorable subgraph with maximum cardinality in a given graph. This paper is an in-depth analysis of the M$k$CS problem that considers various semidefinite programming relaxations including their theoretical and numerical comparisons. To simplify these relaxations we exploit the symmetry arising from permuting the colors, as well as the symmetry of the given graphs when applicable. We also show how to exploit invariance under permutations of the subsets for other partition problems and how to use the M$k$CS problem to derive bounds on the chromatic number of a graph. Our numerical results verify that the proposed relaxations provide strong bounds for the M$k$CS problem, and that those outperform existing bounds for most of the test instances.
