The maximum stable set problem in perfect graphs

Abstract

Maximum Stable Set (MSS) problem is a well-known problem in graph theory. It is an NP-hard problem in general graphs and it has been extensively studied due to both its theoretical and practical importance. On the other hand, when MSS problem is limited to a class of graphs, called perfect graphs, it is polynomially solvable through a Semide nite programming (SDP)-based algorithm. However, SDP solvers are known to be slow especially in larger problems, leading us to question the e ciency of the SDP-based algorithms. Moreover, there has been only limited number of studies examining the MSS problem solely in perfect graphs. Motivated by these, in this thesis, our objective is to compare performances of di erent algorithms with the SDP-based algorithm in perfect graphs. With this objective, we develop cutting plane algorithms that can solve MSS problem in perfect graphs. Additionally, investigate an existing branch-and-bound algorithm to see the performance of a powerful algorithm designed for MSS problem in general graphs. Then, we compare SDP-based algorithm with this branch-and-bound and our cutting plane algorithms using a number of perfect graph instances. Our comparison shows that the cutting plane algorithms perform considerably better than the other algorithms.