Verallgemeinernde Prinzipien für multivariate Algorithmen

• Antragsteller: Professor Dr. Sebastian Siebertz
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2020
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 446200270

Die Untersuchung und Klassifizierung der Komplexität algorithmischer Probleme ist eine der größten Herausforderungen der theoretischen Informatik. Eine zentrale Frage lautet wann, wie und warum algorithmische Probleme effizient gelöst werden können. Um diese Frage zufriedenstellend zu beantworten, suchen Wissenschaftler nach möglichst einheitlichen und allgemeinen Erklärungen für die effiziente Lösbarkeit der Probleme. So wurden in der Algorithmentheorie starke vereinheitlichende Ergebnisse, sogenannte algorithmische Meta-Theoreme, gefunden, die allgemeine mathematische Bedingungen beschreiben, die die automatische Ableitung effizienter Algorithmen ermöglichen. Diese Bedingungen verbinden meist syntaktische Eigenschaften der Probleme (ihre deskriptive Komplexität mittels Logik) und strukturelle Eigenschaften der Eingabeinstanzen (mittels Kombinatorik). Algorithmische Meta-Theoreme sind wertvoll, weil sie ein tiefes Verständnis der algorithmischen Komplexität großer Problemklassen ermöglichen. Das beantragte Projekt zielt darauf ab, das vereinheitlichende Potential algorithmischer Meta-Theoreme für diskrete Algorithmen aufzudecken und voll auszuschöpfen. Dabei soll insbesondere im Framework der parametrisierten Komplexitätstheorie gearbeitet werden, in dem die Laufzeiten von Algorithmen nicht nur im Bezug auf die Eingabegröße, sondern auch im Bezug auf weitere wichtige Sekundärparameter gemessen wird. Dieser multivariate Ansatz ermöglicht eine flexible Berücksichtigung der deskriptiven (logischen) und strukturellen Bedingungen, die typischerweise in algorithmischen Meta-Theoremen auftreten. Die parametrisierte Komplexitätstheorie ist eine voll entwickelte Disziplin der theoretischen Informatik und bietet ein großes Arsenal an algorithmischen Techniken und Paradigmen. Die systematische Weiterentwicklung dieser Techniken und Paradigmen zu algorithmischen Meta-Theoremen ist eine anspruchsvolle Herausforderung, die einen qualitativen Sprung von der Untersuchung konkreter Probleme bis hin zur Beschreibung allgemeiner algorithmischer Theorien erfordert.Im Projekt soll das meta-algorithmische Potential der fortgeschrittensten Techniken der parametrisierten Komplexitätstheorie herausgearbeitet und genutzt werden. Es sollen algorithmische Meta-Theoreme für große Problemklassen in verschiedensten algorithmischen Kontexten erarbeitet werden. Die Ergebnisse sollen einen wesentlicher Beitrag zu einer vereinheitlichenden algorithmischen Theorie im Bereich der parametrisierten Komplexität und darüber hinaus leisten.

• DFG-Verfahren: Sachbeihilfen
• Internationaler Bezug: Frankreich
• Partnerorganisation: Agence Nationale de la Recherche / The French National Research Agency
• Kooperationspartner: Professor Dr. Dimitrios Thilikos Touloupas