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.

## StableSets

### Stable sets and special graph classes

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.

#### Rank-perfect and weakly rank-perfect graphs

The polynomial time solvability of the stable set problem for perfect graphs relies on a polynomial time separation algorithm for a class of inequalities containing all non-trivial facets of their stable set polytopes, the so-called clique constraints. Following a suggestion of Grötschel, Lovasz, and Schrijver (1988), one may relax the notion of perfectness by generalizing clique constraints to other classes of inequalities and investigating all graphs whose stable set polytopes admit such inequalities as only non-trivial facets.

A natural generalization of clique constraints are so-called rank constraints and weak rank constraints, the corresponding superclassesof perfect graphs are the rank-perfect and weakly rank-perfect graphs, introduced by Wagler (2000). There are several classes of rank-perfect and weakly rank-perfect graphs known from the literature, see Wagler (2002) for a survey. In particular, the investigation of the stable set polytopes of graphs with circular structure, called webs and antiwebs, revealed that antiwebs are rank-perfect (Wagler 2003) whereas webs are far from having this property (see Pecher and Wagler 2003). It is an open question whether webs are at least weakly rank-perfect.

#### Normal graphs and the Normal Graph Conjecture

Normal graphs form an information theoretic superclass of perfect graphs and can be seen as closure of perfect graphs by means of co-normal products (Körner 1973) and graph entropy (Cziszar et al. 1990).

Perfect graphs have been recently characterized as those graphs without odd holes and odd antiholes (Strong Perfect Graph Theorem, Chudnovsky et al. 2002). In analogy, Körner and de Simone conjectured that the non-existence of the three smallest odd holes and odd antiholes implies normality (Normal Graph Conjecture, Körner and de Simone 1999). We showed that the Normal Graph Conjecture is asymptotically true and verified it for two first graph classes: webs and antiwebs (Wagler 2004). Proving or disproving the Normal Graph Conjecture in general is subject of our investigations.

#### Imperfection ratio and stable multi-sets

Recently both the imperfection ratio and the imperfection index of graphs has been studied and compared. In this context, also the extreme points of the clique relaxation of the stable set polytope have been revisited.

An evident generalization of stable sets are so-called stable multi-sets introduced by Koster and Zymolka (2002). In joint work with the project "Stable multi-sets", we focus on properties of the stable multi-set polytope as well as its linear relaxation, addressing both theoretical and computational aspects (see Koster and Zymolka 2003). Many of the results are motivated by known results for the stable set problem and provide a deeper insight to the latter.

### Publications

2006
The extreme points of QSTAB(G) and its implications ZIB-Report 06-30 (An extended abstract appeared under the title "On Determining the Imperfection Ratio" in: Electronic Notes in Discrete Mathematics 25 (2006) 177-181) Arie M.C.A. Koster, Annegret Wagler
Stable sets and special graph classes
2005
Comparing Imperfection Ratio and Imperfection Index for Graph Classes ZIB-Report 05-50 (Appeared in: RAIRO-Oper. Res. 42 (2008) 485-500) Arie M.C.A. Koster, Annegret Wagler
Stable sets and special graph classes
2004
The Normal Graph Conjecture is true for Circulants ZIB-Report 04-06 (Appeared in: Graph Theory : Trends in Mathematics. Birkhäuser (2006) 365-374) Annegret Wagler
Stable sets and special graph classes
2003
A construction for non-rank facets of stable set polytopes of webs ZIB-Report 03-21 (Appeared in: European Journal of Combinatorics 27 (2006) 1172-1185) Arnaud Pêcher, Annegret Wagler
Stable sets and special graph classes
On Non-Rank Facets of Stable Set Polytopes of Webs with Clique Number Four ZIB-Report 03-01 (Appeared in: Discrete Applied Mathematics 154 (2006) 1408-1415) Arnaud Pecher, Annegret Wagler
Stable sets and special graph classes
Polyhedral Investigations on Stable Multi-Sets ZIB-Report 03-10 (Appeared under the title "On Cycles and the Stable Multi-Set Polytope" in: Discrete Optimization 2 (2005) 241-255) Arie M.C.A. Koster, Adrian Zymolka
Stable sets and special graph classes
2002
Antiwebs are Rank-Perfect ZIB-Report 02-07 (Appeared in: 4OR 2 (2004) 149-152) Annegret Wagler
Stable sets and special graph classes
Relaxing Perfectness: Which Graphs are 'Almost' Perfect? ZIB-Report 02-03 (Appeared in: The Sharpest Cut - The Impact of Manfred Padberg and His Work. M. Grötschel (ed.) MPS-SIAM Series on Optimiztion, 2004, pp. 77-96) Annegret Wagler
Stable sets and special graph classes
2001
Rank-Perfect and Weakly Rank-Perfect Graphs ZIB-Report 01-18 (Appeared in: Math. Meth. of Oper. Res. 95 (2002) 127-149) Annegret Wagler
Stable sets and special graph classes
2000
Stable Multi-Sets ZIB-Report 00-36 (Appeared in: Mathematical Methods of Operations Research 56 (2002) 45 - 65) Arie M.C.A. Koster, Adrian Zymolka
Stable sets and special graph classes