On different Versions of the Exact Subgraph Hierarchy for the Stable Set Problem
share
One of many different hierarchies towards the stability number of a graph is the exact subgraph hierarchy (ESH). On the first level it starts to compute the Lovász theta function as a semidefinite program (SDP) with a matrix variable of order n+1 and n+m+1 constraints, where n is the number of vertices and m is the number of edges of a graph G. On the k-th level of the ESH it adds all exact subgraph constraints (ESC) for subgraphs of G with k vertices to the SDP. These ESCs make sure that the submatrix of the matrix variable corresponding to the subgraphs are in the appropriate polytopes. In order to exploit the ESH computationally one only includes ESCs for certain wisely chosen subgraphs. In this paper we introduce a variant of the ESH that starts with an alternative SDP to compute the Lovász theta function with a matrix variable of order n and only m+1 constraints. We show that it makes sense to include the ESCs into this SDP and build the compressed ESH (CESH) analogously to the ESH. Computationally the CESH seems favorable as the SDP is smaller. However, we prove that the bounds obtained with the ESH are always at least as good as those of the CESH. In computations 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.
READ FULL TEXT