Stabile Mengen und spezielle Graphenklassen

• Antragsteller: Professor Dr. Martin Grötschel
• Fachliche Zuordnung: Mathematik
• Förderung: Förderung von 2001 bis 2010
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 5467699

Stabile Mengen in Graphen bilden eines der wichtigen Modelle in der ganzzahligen Optimierung. Anwendung finden stabile Mengen z.B. bei der ÖPNV-Dienstplanung, beim Airline Crew-Scheduling und gewissen Fahrzeugeinsatzplanungen. Das Stabile-MengenProblem ist jedoch i.A. NP-schwer. Die polynomiale Lösbarkeit des Stabile-Mengen-Problems ist nur für wenige Graphenklassen bekannt. Unter diesen sind perfekte Graphen die strukturell interessantesten: Charakterisierungen perfekter Graphen bilden eine Schnittstelle zwischen Graphentheorie, Polyedertheorie, Informationstheorie sowie ganzzahliger Programmierung und liefern Einblicke in Zusammenhänge dieser Gebiete. Der Schwerpunkt dieses Projektes liegt auf zwei Verallgemeinerungen des Perfektheitsbegriffes: hinsichtlich der polyedertheoretischen und hinsichtlich der informationstheoretischen Charakterisierung perfekter Graphen. Ein Gegenstand der Untersuchung sind strukturelle Eigenschaften und Stabile-Mengen-Polytope von Klassen "fast" perfekter Graphen und von Oberklassen perfekter Graphen im polyedertheoretischen Sinne. Dadurch soll, wenn möglich, die Zahl der Graphenklassen erhöht werden, für die polynomiale Lösbarkeit des Stabile-Mengen-Problems bewiesen werden kann. In Zusammenarbeit mit der Arbeitsgruppe Ziegler ist weiter das Studium der Struktur von 0/1-Polytopen am Beispiel von StabileMengen-Polytopen geplant. Eine informationstheoretische Oberklasse perfekter Graphen bilden die normalen Graphen, basierend auf schwacher Additivität der Graph-Entropie. Wie sich diese Erweiterung des Perfektheitsbegriffes graphen- bzw. polyedertheoretisch auswirkt und welche Bedeutung dabei den Wahrscheinlichkeitsverteilungen zukommt, ist Gegenstand der Zusammenarbeit mit der Arbeitsgruppe Prömel.

• DFG-Verfahren: Forschungsgruppen
• Teilprojekt zu: FOR 413: Algorithmen, Struktur, Zufall