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.

Ce séminaire vous permettra d’échanger avec le conférencier et les chercheurs présents autour de boissons et de collations. Nous vous remercions de confirmer votre présence.

Entrée gratuite. Bienvenue à tous!