论文标题
图形和半决赛等级
Graph Coloring and Semidefinite Rank
论文作者
论文摘要
本文考虑了半决赛编程，矩阵等级和图形着色之间的相互作用。 Karger，Motwani和Sudan \ cite {KMS98}给出了一个向量程序，该程序可以将图形的颜色编码为低级的半芬属矩阵。通过半决赛编程的互补松弛条件，如果最佳双重解决方案具有足够高的排名，则任何最佳原始解决方案都必须具有较低的等级。我们试图表征可以证明相应的双最佳解决方案必须具有足够高的级别的图表。对于原始的Karger，Motwani和Sudan Vector程序，我们表明，任何$ K $ -Tree的图都具有足够高的双重等级，并且我们可以从相应的低级别原始解决方案中提取着色。我们还可以证明，如果图形不是独特的色彩，那么就不会有足够高的级别双最佳解决方案。这使我们能够完全表征双重最佳解决方案具有足够高的双重等级的平面图。然后，我们修改半决赛程序以具有成本的目标函数，并探索何时可以创建一个成本函数，其最佳双重解决方案的排名足够高。我们表明，鉴于图形着色，始终可以构建这种成本函数。成本函数的构建产生了图形着色的启发式词，我们在平面图的情况下表现出了很好的作用。我们的研究是由Colin deverdière图不变的\ cite {cdv90}（以及相应的Colin deverdière的猜想），其中与双重可行矩阵具有相似性的矩阵在图中必须具有很高的级别。我们探讨了猜想和双重解决方案等级之间的联系。
This paper considers the interplay between semidefinite programming, matrix rank, and graph coloring. Karger, Motwani, and Sudan \cite{KMS98} give a vector program for which a coloring of the graph can be encoded as a semidefinite matrix of low rank. By complementary slackness conditions of semidefinite programming, if an optimal dual solution has sufficiently high rank, any optimal primal solution must have low rank. We attempt to characterize graphs for which we can show that the corresponding dual optimal solution must have sufficiently high rank. In the case of the original Karger, Motwani, and Sudan vector program, we show that any graph which is a $k$-tree has sufficiently high dual rank, and we can extract the coloring from the corresponding low-rank primal solution. We can also show that if the graph is not uniquely colorable, then no sufficiently high rank dual optimal solution can exist. This allows us to completely characterize the planar graphs for which dual optimal solutions have sufficiently high dual rank. We then modify the semidefinite program to have an objective function with costs, and explore when we can create a cost function whose optimal dual solution has sufficiently high rank. We show that it is always possible to construct such a cost function given the graph coloring. The construction of the cost function gives rise to a heuristic for graph coloring which we show works well in the case of planar graphs. Our research was motivated by the Colin de Verdière graph invariant \cite{CDV90}(and a corresponding conjecture of Colin de Verdière), in which matrices that have some similarities to the dual feasible matrices must have high rank in the case that graphs are of a certain type. We explore the connection between the conjecture and the rank of the dual solutions.
