A class of new cutting planes for SDP relaxations of stable set and c...

Stable set and colouring problems are fundamental combinatorial optimization problems. A standard method in combinatorial optimization is to write a problem as a linear problem with integer variables, and then to consider its relaxation in order to get bounds on the optimal solution. This research focuses on bounds which are obtained by semidefinite relaxations using semidefinite programming. A famous semidefinite relaxation for both stable set and colouring problems is the Lovász theta function. We consider tightening of the Lovász theta function which can be achieved by adding valid inequalities into the formulation. We combine the ideas of some of the existing inequalities and derive new cutting planes for both problems. Finally, we investigate the bounds obtained by adding the proposed inequalities. We compare our bounds with existing relaxations and present computational results.