论文标题
在不同版本的稳定集问题的确切子图层次结构上
On different Versions of the Exact Subgraph Hierarchy for the Stable Set Problem
论文作者
论文摘要
让$ g $是$ n $顶点和$ m $边缘的图。确切的子图层次结构（ESH）的稳定性数字的几个层次结构之一。在第一个级别上，它将LovászTheta函数$ \ vartheta（g）$作为半芬特程序（SDP），其矩阵变量$ n+1 $ $ 1 $和$ n+m+1 $约束。在$ k $ -th级别上，它将订单$ k $子图的所有确切子图限制（ESC）添加到SDP。 AS ESC可确保与该子图相对应的矩阵变量的子序列在正确的polytope中。通过仅包括一些ESC中的SDP，可以通过计算来利用ESH。 在本文中，我们介绍了ESH的一个变体，该变体通过SDP计算$ \ vartheta（g）$，其矩阵变量$ n $和$ m+1 $约束。我们表明，将ESC包括在此SDP中是有意义的，并将压缩的ESH（CESH）类似地引入ESH。在计算上，由于SDP较小，因此CESH似乎有利。但是，我们证明，基于ESH的界限始终与库什的界限一样好。在计算实验中，有时它们会明显更好。 我们还引入了缩放的ESC（SESC），这是将精确性约束包含到较小的SDP中的更自然的方法，我们证明，包括SESC等同于在每个子图中包括ESC。
Let $G$ be a graph with $n$ vertices and $m$ edges. One of several hierarchies towards the stability number of $G$ is the exact subgraph hierarchy (ESH). On the first level it computes the Lovász theta function $\vartheta(G)$ as semidefinite program (SDP) with a matrix variable of order $n+1$ and $n+m+1$ constraints. On the $k$-th level it adds all exact subgraph constraints (ESC) for subgraphs of order $k$ to the SDP. An ESC ensures that the submatrix of the matrix variable corresponding to the subgraph is in the correct polytope. By including only some ESCs into the SDP the ESH can be exploited computationally. In this paper we introduce a variant of the ESH that computes $\vartheta(G)$ through an SDP with a matrix variable of order $n$ and $m+1$ constraints. We show that it makes sense to include the ESCs into this SDP and introduce the compressed ESH (CESH) analogously to the ESH. Computationally the CESH seems favorable as the SDP is smaller. However, we prove that the bounds based on the ESH are always at least as good as those of the CESH. In computational experiments sometimes they are significantly better. We also introduce scaled ESCs (SESCs), which are a more natural way to include exactness constraints into the smaller SDP and we prove that including an SESC is equivalent to including an ESC for every subgraph.
