Grundlagen der effizienten Modellprüfung für Zähllogiken auf strukturell dünnen Graphklassen

• Antragsteller: Professor Dr. Peter Rossmanith
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2019 bis 2023
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 426003173

Viele Entscheidungs- und Optimierungsprobleme auf Graphen und Datenbanken lassen sich in geeigneten Logiken ausdrücken.Meta-Algorithmen sind Algorithmen, die nicht auf ein bestimmtes Problem beschränkt sind. Sie können alle Probleme lösen, die sich durch gewisse logische Formeln ausdrücken lassen, was sie zu einem sehr flexiblem Werkzeug macht.Es sind bereits mehrere solcher Meta-Algorithmen bekannt. Für die Prädikatenlogik erster Stufe können entsprechende Probleme effizient auf bestimmten Graphklassen gelöst werden, sofern diese Graphklassen gewisse strukturelle Eigenschaften besitzen. Für die ausdrucksstärkere monadische Logik zweiter Ordnung gibt es ebenfalls solche Algorithmen, welche aber nur auf stärker eingeschränkten Graphklassen arbeiten.In Zählproblemen spielen die Anzahl und Größe verschiedener Mengen eine Rolle. Sie können in klassischer Prädikatenlogik nicht oder nur eingeschränkt modelliert werden, spielen aber in der Praxis eine wichtige Rolle. Um Zählprobleme zu modellieren, können entsprechende Zähllogiken definiert werden. Aus den letzten Jahren gibt es auch auf diesem Gebiet einige Ergebnisse, wobei aber viele Fragen noch offen blieben.In diesem Projekt soll untersucht werden, welche Zählprobleme auf welchen Graphklassen durch Meta-Algorithmen effizient gelöst werden können. Dabei wollen wir zwischen exaktem und approximativem Zählen unterscheiden und auch verwandte Themen wie Aufzählalgorithmen behandeln. Neben dem Entwurf effizienter Algorithmen sollen auch stets passende untere Schranken bewiesen werden. Dieses Vorgehen soll mit den folgenden drei Problemen als Grundstein begonnen werden:Wir wollen eine aussagekräftige Zähllogik betrachten, für die bereits bekannt ist, dass man sie auf sehr beschränkten Graphklassen nicht exakt auswerten kann. Für diese Logik wollen wir einen aproximativen Auswertungsalgorithmus entwickeln.Des weiteren wollen wir Meta-Algorithmen für Zählprobleme mit Paritätsbedingungen angeben, indem wir die Erweiterung der Prädikatenlogik um Modulo-Zählen untersuchen.Das Problem Partial Dominating Set sucht nach einer Menge von Knoten, die die Hälfte des Graphen dominieren. Wir betrachten eine Zähllogik, die dieses und ähnliche Probleme beschreiben kann. Auf diese Weise wollen wir verschiedene Dominierungs- und Überdeckungsprobleme auf möglichst allgemeinen Graphklassen effizient lösen.

• DFG-Verfahren: Sachbeihilfen