Semidefinite programming and eigenvalue bounds for the graph partition problem
Semidefinite programming and eigenvalue bounds for the graph partition problem
复制标题
图划分问题的半定规划和特征值界
作者：
E. V. Dam;R. Sotirov
图划分问题是将图的顶点集划分为固定数量的给定大小的集合，使得连接不同集合的边的权重之和最优化的问题。在本文中，我们简化了一个已知的矩阵提升半定规划放松的图划分问题的几类图，也展示了如何聚合额外的三角形和独立集的约束，对称图。给出了强正则图的图划分问题的特征值界，推广了均分问题的一个类似结果。对于某些约翰逊图和Kneser图，我们还得到了图划分问题的线性规划界.使用我们所谓的拉普拉斯代数的一个图，我们推导出的特征值界的图划分问题，这是第一个已知的封闭形式的限制，适用于任何图形，从而扩展了一个众所周知的结果在谱图论。最后，我们加强了一个已知的半定规划松弛的一个特定的二次分配问题和上述矩阵提升半定规划松弛通过添加两个约束，对应于分配两个顶点的图的不同部分的分区。当其他松弛提供弱或平凡的界限时，这种加强在高度对称图上表现良好。
The graph partition problem is the problem of partitioning the vertex set of a graph into a fixed number of sets of given sizes such that the sum of weights of edges joining different sets is optimized. In this paper we simplify a known matrix-lifting semidefinite programming relaxation of the graph partition problem for several classes of graphs and also show how to aggregate additional triangle and independent set constraints for graphs with symmetry. We present an eigenvalue bound for the graph partition problem of a strongly regular graph, extending a similar result for the equipartition problem. We also derive a linear programming bound of the graph partition problem for certain Johnson and Kneser graphs. Using what we call the Laplacian algebra of a graph, we derive an eigenvalue bound for the graph partition problem that is the first known closed form bound that is applicable to any graph, thereby extending a well-known result in spectral graph theory. Finally, we strengthen a known semidefinite programming relaxation of a specific quadratic assignment problem and the above-mentioned matrix-lifting semidefinite programming relaxation by adding two constraints that correspond to assigning two vertices of the graph to different parts of the partition. This strengthening performs well on highly symmetric graphs when other relaxations provide weak or trivial bounds.