Cliquen in hyperbolischen und gewichteten geometrischen Graphen

• Antragsteller: Professor Dr. Thomas Bläsius
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2023
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 524989715

Der Kernunterschied zwischen Theorie und Praxis im Bereich der Algorithmik besteht darin, dass theoretische Analysen meist auf Garantien abzielen, die für beliebige Eingaben gelten, wohingegen tatsächliche Implementierungen typischerweise auf praxisrelevanten Instanzen evaluiert werden. Ziel des Projekts ist es, diese Lücke zwischen Theorie und Praxis zu verkleinern. Dazu untersuchen wir Eingabemodelle, die praktischen Daten aus verschiedenen Anwendungsbereichen bezüglich wichtiger struktureller Eigenschaften ähneln. Das ermöglicht es uns, die algorithmischen Implikationen dieser Eigenschaften in einem idealisierten Setting theoretisch zu untersuchen, was dann wiederum zur Entwicklung in der Praxis effizienter Algorithmen beiträgt. Der Fokus dieses Projekts liegt dabei auf Cliquen in Graphen mit zugrundeliegender Geometrie. Dabei betrachten wir die hyperbolische Geometrie beziehungsweise gewichtete Punkte und Distanzen, was heterogene Gradverteilungen ermöglicht. Neben Einsichten zur Struktur von Cliquen planen wir die Untersuchung algorithmischer Implikationen dieser strukturellen Einsichten. Darüber hinaus wollen wir evaluieren, wie gut unsere Eingabemodelle praktische Eingaben repräsentieren. Im Kern geht es um die Beantwortung der folgenden drei Fragen: Was ist die Cliquenstruktur in Graphen mit zugrundeliegender hyperbolischer beziehungsweise gewichteter Geometrie? Welche algorithmischen Implikationen haben diese strukturellen Einsichten? Wie gut übersetzen sich unsere Resultate der idealisierten Eingabemodellen zu Eingaben aus der Praxis?

• DFG-Verfahren: Sachbeihilfen