Stable sets in graphs form one of the important models in integer programming and have various applications. However, the stable set problem is NP-hard and also not easy to treat in practice.

The polynomial time solvability of the stable set problem is known for a few graph classes only. Among them, perfect graphs admit the most interesting structure since different characterizations of perfect graphs provide an interface between graph theory, polyhedral theory, information theory, and integer programming and reveal, thereby, insight in the relation of these areas.

Perfect graphs are, e.g., characterized by means of graph entropy, the imperfection ratio of a graph can be expressed via the graph entropy, and the graph entropy by means of stable set polytopes - showing the interaction between the three concepts.

The subject of this project within the framework of the DFG research group "Algorithms, Structur, Randomness" is to relax and generalize the concepts involved in the three characterizations of perfect graphs: Rank-perfect graphs form a superclass of perfect graphs w.r.t. the stable set polytope, normal graphs w.r.t. the graph entropy. The aim is to explore which of the important properties of perfect graphs these superclasses share. Moreover, in joint work with the project "Stable multi-sets" the study of stable set problem and polytope should be extended to the more general concept of stable multi-sets.

• Annegret K. Wagler, Univ. Magdeburg,
• Illya V. Hicks, Texas A & M University