UNISTRUC: Vereinheitlichung struktureller Grundlagen der Algorithmik

• Antragsteller: Dr. Jan Dreier
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2026
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 563448077

KONTEXT: Die Bewältigung algorithmischer Probleme mit hoher Worst-Case-Komplexität stellt eine zentrale Herausforderung der Informatik dar. Ziel dieses Projekts ist es, Eingabeinstanzen zu charakterisieren, auf denen viele dieser schwierigen algorithmischen Probleme effizient lösbar sind. Nešetřil und Ossona de Mendez führten den Begriff der nowhere-dense Graphklassen ein. Dieser Begriff verallgemeinert unter anderem planare Graphen sowie Graphen mit beschränktem Grad oder ausgeschlossenem Minor. Grohe, Kreutzer und Siebertz zeigten, dass nowhere-dense Klassen algorithmisch handhabbar sind: Alle Probleme, die sich in First-Order-Logik ausdrücken lassen, können auf diesen Klassen in nahezu linearer Zeit gelöst werden. Kürzlich haben wir dieses Ergebnis auf monadically stable Graphklassen erweitert – einen zentralen Begriff aus der Modelltheorie, der über die klassische Sparsity-Theorie hinausgeht. In letzter Zeit haben auch Graphklassen mit beschränkter twin-width große Aufmerksamkeit erhalten. Diese Klassen sind mit monadically stable und nowhere-dense Klassen unvergleichbar, jedoch ebenfalls algorithmisch handhabbar. Zusammenfassend wurde über die Jahre intensiv daran gearbeitet, immer größere Klassen von Graphen zu identifizieren, die algorithmisch handhabbar sind. Derzeit markieren Graphklassen mit beschränkter twin-width und monadisch stabile Klassen die Grenze der Traktabilität. FORSCHUNGSFRAGEN: Twin-width und monadic stability sind zwei fundamental unterschiedliche Konzepte. Ziel dieses Projekts ist es, eine einheitliche Theorie der algorithmischen Traktabilität zu entwickeln, welche twin-width und monadic stability verallgemeinert und die (hereditären) algorithmisch handhabbaren Graphklassen genau charakterisiert. Ein zentraler Ansatz besteht darin, zu zeigen, dass First-Order Model Checking auf monadically dependent Graphklassen fixed-parameter tractable ist. METHODEN: Das Projekt vereint Techniken aus der Sparsity-Theorie, der endlichen Modelltheorie, der Stabilitätstheorie und der Twin-width-Theorie, um nützliche kombinatorische Strukturen in Graphen zu identifizieren. Diese Strukturen sollen genutzt werden, um effiziente Graphzerlegungen zu berechnen. Der Fokus liegt auf Eigenschaften wie uniform quasi-wideness, flip-flatness oder flip-breakability, auf Pursuit-Evasion-Spielen wie dem Flipper-Spiel oder dem flip-width-Spiel sowie auf Model-Checking-Methoden für nowhere-dense und monadically stable Graphklassen. INNOVATION: Das Projekt zielt darauf ab, die zentralen Erkenntnisse der Sparsity-Theorie, Twin-width-Theorie und Stabilitätstheorie zu vereinen und systematisch weiterzuentwickeln. Die erwarteten Ergebnisse könnten erheblichen Einfluss auf zentrale Bereiche der theoretischen Informatik haben, insbesondere in den Bereichen Logik, Graphentheorie und parametrisierte Komplexität.

• DFG-Verfahren: Emmy Noether-Nachwuchsgruppen