Platzeffiziente Graphalgorithmen 2

• Antragsteller: Professor Dr. Frank Kammer
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2017
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 379157101

Die Ziele des Antrags sind zweigeteilt. Einerseits konzentriert sich unsere Arbeit auf neue platzsparende parametrisierte Algorithmen und Approximationsalgorithmen für die Ausführung auf einer CPU und mit Anpassungen auch auf einer GPU, wo Platzbeschränkungen häufig ein Hauptproblem sind (Rhu et al., MICRO 2016). Algorithmen auf einer GPU oder hybride Algorithmen (CPU und GPU) sind von besonderem Interesse in der künstlichen Intelligenz, wo z.B. aktuelle Ergebnisse zeigen, dass parametrisierte Algorithmen helfen können, das Training in Bayes'schen Netzwerken zu beschleunigen (Scanagatta et al., NeurIPS 2016). Auf der anderen Seite werden viele Probleme in der Bioinformatik auf Systemen mit 128 GB oder viel mehr RAM durch Verwendung von Tools gelöst, die auf (temporalen) Graph-Algorithmen basieren -- Wieder ist ein wesentliches Problem der Anwendungen der Platzbedarf der verwendeten (temporalen) Graph-Algorithmen (Strasser et al., ESA 2020).Im Detail besteht ein Kernbereich unserer Ziele darin, den Platzbedarf von weiteren FPT-Algorithmen (z.B. mit den Parametern Treedepth, Cliquewidth oder Outerplanarity Index) sowie Näherungsalgorithmen (z.B. Baker's PTAS) zu reduzieren. Im Gegensatz zu früheren Untersuchungen zielen wir jetzt auch auf spezielle Graphklassen (wie planare, chordale und unit-disk Graphen) ab, ihre Erkennung sowie spezielle Datenstrukturen für diese Graphklassen (z.B. berechnen, speichern und zugreifen von planaren Einbettungen). Eine weitere Forschungsrichtung in diesem Bereich ist die Reduzierung des Platzverbrauchs von Algorithmen basierend auf der sogenannten Bidimensional-Theorie. Als praktische Anwendung wollen wir Anpassungen unserer platzsparenden Algorithmen für GPUs finden und so Lösungen im Bereich der künstlichen Intelligenz verbessern. Unsere Anpassungen können auch eine Unterstützung aktueller Ansätze für Graphen Neuronale Netzwerke (GNN) zur Lösung kombinatorischer Probleme sein (Sato et al., NeurIPS 2019). Ein zweiter Kernbereich der hier vorgestellten Zielrichtung sind temporale Graphen und deren Big-Data-Anwendungen wie z.B. Straßennetze (Gendreau et al., Comput. Oper. Res. 2015) und Teile der Bioinformatik, wo zeitliche Graphen verwendet werden, um die Ähnlichkeit von Biomolekülen mit sich im Laufe der Zeit ändernden Verbindungen widerzuspiegeln (Han et al., Nature 2004). Viele Probleme auf einem temporalen Graphen können durch eine einfache Transformation auf einen "Standard"-Graphen gelöst werden. Der Fokus auf diesen Transformationen ist normalerweise nur die Zeiteffizienz. Ist n die Anzahl von Knoten und tau die Anzahl der Zeitschritte des temporalen Graphen, dann führt die Transformation normalerweise Theta(n tau) neue Knoten ein. Wendet man anschließend einen (platzsparenden) Graph-Algorithmus auf dem transformierten Graphen an, dann werden üblicherweise Omega(n tau) Bits benötigt. Neue Ansätze sind notwendig, um mit weniger Platz auszukommen.

• DFG-Verfahren: Sachbeihilfen