The stable set problem is a well-known combinatorial optimization problem. It is NP-complete and furthermore hard to approximate, hence one wants to get tight upper bounds for the stability number. One possible upper bound is given by the Lovász theta function, which can be computed as semidefinite program. In order to improve this upper bound, we will add additional constraints to the Lovász theta function, namely exact subgraph constraints. 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. The talk will give a motivation, why exact subgraph constraints should be considered, address the question of how to choose the subgraphs to be added as exact subgraph constraints and eventually have a look on computational results.

This seminar will give you the opportunity to meet the speaker and all the researchers in attendance while enjoying drinks and snacks. We would highly appreciate if you could confirm your attendance.

Free entrance. Welcome to everyone!