Effizientere Algorithmen für polynomialzeitlösbare Graphprobleme

• Antragsteller: Dr. André Nichterlein, seit 5/2022
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2017 bis 2023
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 327762855

Das zentrale Projektziel ist die Entwicklung neuer, für wichtige Spezialfälle beschleunigter Algorithmen für polynomialzeitlösbare Graphprobleme. Dabei sollen praxisuntaugliche Polynomgrade in den Laufzeiten der bekannten Algorithmen dadurch ausgehebelt werden, dass die Grundidee der parametrisierten Algorithmik für NP-schwere Probleme, die Miteinbeziehung problemspezifischer Parameter beim Algorithmenentwurf und der Laufzeitanalyse, übertragen und ausgebaut wird. Im Vordergrund steht die Entwicklung von (Quasi-)Linerarzeitalgorithmen im Falle konstanter Parameterwerte (wie z.B. maximaler Knotengrad oder Baumweite des zugrundeliegenden Graphen). Eventuell könnten so auch in letzter Zeit entwickelte "Untere-Schranken-Ergebnisse" zu superlinearen Laufzeiten zur Lösung diverser Graphprobleme (wie z.B. ALL PAIRS SHORTEST PATH) überwunden werden. Anders als in der klassischen parametrisierten Algorithmik für NP-schwere Probleme treten einige besondere Aspekte hervor; beispielsweise ist auch eine polynomielle und nicht nur exponentielle Abhängiggkeit vom Parameter möglich. Das Projekt strebt sowohl rein theoretische Grundlagenforschung als auch anwendungsbezogene Forschung bis hin zum Algorithm Engineering für ausgesuchte Probleme an. Die zwei Hauptsäulen des Projekts sind zum einen die Beschleunigung von klassischen Basisgraphalgorithmen (wie Fluss- oder Durchmesserberechnungen) und zum anderen die Beschleunigung von Graphalgorithmen für neuartige Probleme in erster Linie aus dem Kontext der Analyse sozialer Netzwerke (bis hin zu hier eingesetzten Heuristiken). Methodisch im Zentrum stehen die systematische Durchforstung von Parameterräumen, effiziente Datenreduktionen und Problemkerne, "Distance from Triviality"-Parametrisierungen und die Entwicklung von parameterabhängigen "quasilinearzeittauglichen" Datenstrukturen für die jeweiligen Probleme.

• DFG-Verfahren: Sachbeihilfen
• Ehemaliger Antragsteller: Professor Dr. Rolf Niedermeier, bis 5/2022 (†)