Effizienzgrenzen für Graphisomorphie- und Homomorphie-Probleme

• Antragsteller: Dr. Oleg Verbitsky
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2011 bis 2016
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 197227691

Unser Projekt zielt darauf, die aktuellen Grenzen für die effiziente Lösbarkeit von Isomorphie- und Homomorphie- (d.h. Constraint Satisfaction) Problemen für Graphen zu erweitern. Obwohl die beiden Klassen von Problemen im Allgemeinen auf unterschiedlichen Ebenen der Komplexitätshierarchie liegen, setzen wir auf Methoden, mit denen man sie aus einer gemeinsamen Perspektive behandeln kann. Diese Methoden beruhen auf Definierbarkeit der Eingabegraphen in der Logik der ersten Stufe mit endlich vielen Variablen und ihrem existenziell-positiven Fragment. Die Definierbarkeit von Graphen in der Logik mit k Variablen und logarithmischer Quantorentiefe hat zur Folge, dass Isomorphie solcher Graphen durch eine natürliche parallelisierte Version des k-dimensionalen Weisfeiler-Lehman-Algorithmus in NC entscheidbar ist. Dies gilt auch dann, wenn die Syntax durch Anzahlquantoren erweitert wird. Manchmal lässt sich das NC-Ergebnis sogar zu einem Logspace-Algorithmus verbessern, der nicht unmittelbar auf der ursprünglichen Analyse der deskriptiven Komplexität beruht. Mit diesem Ansatz wollen wir neue Effizienzergebnisse für mehrere wichtige Klassen von Graphen erhalten. Die Ausdrucksstärke der existentiell-positiven Logik mit k Variablen korrespondiert zu algorithmischen Techniken für das Homomorphie-Problem, die in der Constraint-Satisfaction-Forschung als k-Konsistenzprüfung bekannt sind. Hier erwarten wir, dass eine gründliche Analyse der deskriptiven Komplexität es uns ermöglichen wird, sowohl neue algorithmische Ergebnisse zu erhalten als auch untere Schranken für die Effizienz der k-Konsistenzprüfung zu etablieren. Die Fälle von k=2,3 entsprechen der Arc- und Pfad-Konsistenz, die als Hauptwerkzeug zur Lösung von Constraint-Satisfaction-Problemen beschränkter Weite dienen. Für Constraint-Satisfaction-Probleme unbeschränkter Weite untersuchen wir den optimalen Wert des Parameters k als Funktion der Eingabegröße und betrachten damit die k-Konsistenzprüfung als einen exakten exponentiellen Algorithmus. Wir planen auch lokal bijektive Homomorphismen (oder Überlagerungsabbildungen) im Rahmen ihrer Anwendungen auf verschiedene Modelle von lokalen und verteilten Berechnungen zu untersuchen.

• DFG-Verfahren: Sachbeihilfen