Stabile Mengen in Graphen bilden eines der wichtigen Modelle in der ganzzahligen Optimierung. Sie haben vielfältige Anwendungen. Das Stabile-Mengen-Problem ist im Allgemeinen NP-schwer und auch in der Praxis nicht einfach zu lösen.

Die polynomiale Lösbarkeit des Stabile-Mengen-Problems ist nur für wenige Graphenklassen bekannt. Unter diesen sind perfekte Graphen die strukturell interessantesten, da Charakterisierungen perfekter Graphen eine Schnittstelle zwischen Graphentheorie, Polyedertheorie, Informationstheorie und ganzzahliger Programmierung bilden und Einblicke in Zusammenhänge dieser Gebiete liefern.

Perfekte Graphen sind u.a. mittels der Graph-Entropie charakterisiert; der sog. Imperfektheitsgrad kann durch die Graph-Entropie ausgedrückt werden, die Graph-Entropie wiederum als Entropie des Stabile-Mengen-Polytops. Dies zeigt den engen Zusammenhang zwischen polyedertheoretischen und informationstheoretischen Charakterisierungen perfekter Graphen.

Der Schwerpunkt des Projektes im Rahmen der DFG-Forschergruppe "Algorithmen, Struktur, Zufall" liegt auf der Untersuchung von Relaxierungen dieser Konzepte auf Oberklassen perfekter Graphen: Rang-perfekte Graphen bilden eine Oberklasse perfekter Graphen bzgl. des Stabile-Mengen-Polytops, normale Graphen bzgl. der Graph-Entropie. Unser Interesse gilt u.a. der Frage, welche wichtigen Eigenschaften perfekter Graphen noch für diese Oberklassen gelten. Darüber hinaus wird in Zusammenarbeit mit dem Projekt "Stabile Multimengen" das Studium von Stabile-Mengen-Problem und -Polytop auf das allgemeinere Konzept stabiler Multimengen ausgedehnt.

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