One of Franz’ Most Recent Toys: Exact Subgraph Constraints

Franz is playing with exact subgraph constraints for quite some time now. We will have fun using them for the stable set problem. This is a NP-hard problem, where one wants to find the biggest set of vertices in a graph such that no two vertices are adjacent.

An upper bound on the stability number of a graph is the Lovász theta function, which can be computed in polynomial time as semidefinite program (SDP). One possibility to further improve this upper bound is to include so called exact subgraph constraints into the SDP. For a certain subgraph the exact subgraph constraint ensures, that the submatrix of the calculation of the Lovász theta function corresponding to the subgraph is contained in the convex hull of all stable set matrices of the subgraph.

Recently Franz, Malwina Duda and I are trying to solve the obtained SDP by building the Lagrangian dual with respect to the exact subgraph constraints and applying the bundle method with easy components to the resulting SDP. On our way we will encounter a very nicely structured QP.