Neue Techniken und verbesserte Approximationsalgorithmen für Konnektivitätserweiterungsprobleme

• Antragsteller: Dr. Felix Hommelsheim
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2026
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 573939419

Die Entwicklung robuster und fehlertoleranter Netzwerke stellt eine zentrale Herausforderung in Kommunikations-, Transport- und Energiesystemen dar. In der Praxis genügt es oft, die Konnektivität eines Netzwerks auch bei Ausfall einer einzelnen Verbindung aufrechtzuerhalten, da gleichzeitige Mehrfachausfälle selten sind und ein erster Ausfall in der Regel behoben werden kann, bevor es zu einem weiteren kommt. Dies motiviert die Untersuchung der 2-Kantenzusammenhangseigenschaft – einem besonders praxisrelevanten Maß für Redundanz, das einen sinnvollen Kompromiss zwischen Zuverlässigkeit und Kosten darstellt. Aus theoretischer Sicht gehören das zugehörige 2-kantenzusammenhängende Spannuntergraphproblem (2ECSS) und seine gewichteten Varianten zu den zentralen Fragestellungen der Forschung im Bereich von Approximationsalgorithmen, sind jedoch aufgrund ihrer kombinatorischen Komplexität und APX-Schwere bislang nur unzureichend verstanden. Im Mittelpunkt dieses Projekts steht die Entwicklung verbesserter Approximationsalgorithmen für zentrale Spezialfälle des gewichteten 2ECSS, insbesondere für das ungewichtete 2ECSS sowie das Forest Augmentation Problem. Beide Probleme sind sowohl aus theoretischer als auch aus praktischer Sicht von hoher Relevanz und waren Gegenstand bedeutender jüngerer Fortschritte. Eine zentrale Motivation dieses Antrags ist unser aktuelles Ergebnis – ein 5⁄4-Approximationsalgorithmus für das ungewichtete 2ECSS, angenommen bei STOC 2025 –, das neue strukturelle und kombinatorische Techniken einführt und den Stand der Forschung deutlich weiterentwickelt. Auf diesen Methoden aufbauend, sollen insbesondere das Forest Augmentation Problem und verwandte Varianten weiter untersucht werden. Weitere Ziele sind ein besseres Verständnis der approximativen Grenzen sowie eine Verbesserung bestehender Nicht-Approximierbarkeitsresultate. Der Antrag knüpft an einen zuvor eingereichten DFG-Antrag an, der ähnliche Probleme behandelte, jedoch einen computerunterstützten Beweisansatz verfolgte. Dieser frühere Antrag wurde nicht bewilligt, unter anderem weil nicht ausreichend dargelegt wurde, wie Korrektheit und Implementierung des Beweises sichergestellt werden sollten. Die daraufhin entstandene Forschung führte jedoch direkt zu dem erwähnten STOC-Ergebnis. Im Verlauf dieser Arbeiten wurden neue, rein analytische Methoden entwickelt, die auf den Einsatz von Computerbeweisen verzichten. Der vorliegende Antrag greift diese Entwicklungen auf, weitet den Fokus aus und adressiert die früher geäußerten Kritikpunkte ebenso wie neue Forschungsrichtungen

• DFG-Verfahren: Sachbeihilfen