Dr. Oleg Verbitsky

• Effizienzgrenzen für das Graphisomorphie-Problem

  Quelle ↗

  Das Graphisomorphieproblem (kurz GI) besteht darin, für zwei gegebene Graphen zu entscheiden, ob sie isomorph sind oder nicht. Dieses Problem ist sowohl in der Theoretischen Informatik als auch in derAngewandten Diskreten Mathematik von fundamentaler Bedeutung. Es ist zwar bekannt, dass GI in der Klasse NP liegt, aber der exakte Komplexitätsstatus des Problems ist seit mehreren Dekaden offen. Eingeschränkt auf bestimmte Klassen von Graphen kann das Isomorphieproblem in polynomieller Zeit lösbar oder aber ebenso schwer wie für beliebige Graphen sein. Im letzteren Fall nennt man das Problem GI-vollständig. Unsere allgemeine Zielvorgabe ist es, eine möglichst scharfe Grenzlinie zwischen diesen beiden Fällen zu ziehen. Insbesondere sind hierzu vor allem Graphklassen zu untersuchen, für die das Isomorphieproblem bisher weder als effizient lösbar noch als GI-vollständig klassifiziert werden konnte. Darüber hinaus möchten wir für eine Reihe von in polynomieller Zeit lösbaren Fällen effiziente parallele oder sogar Log-Space Algorithmen finden. Neben der Untersuchung von wichtigen speziellen Graphklassen haben wir vor, hinreichende Bedingungen dafür zu finden, eine gegebene Graphklasse als effizient lösbar oder als GI-vollständig einstufen zu können. Solche Bedingungen können auf unterschiedlichen Eigenschaften der Graphklassen basieren, etwa auf Zerlegbarkeitseigenschaften (bzgl. modularer oder Splitzerlegungen) oder auf Definierbarkeitseigenschaften in beschränkten Logiken sowie auf Wachstumstypen von hereditären Graphklassen.Das Projekt hat enge Querbezüge zur endlichen Modelltheorie (die Definierbarkeitsaspekte), zur topologischen Graphentheorie (Isomorphie von Karten auf Flächen) sowie zur algorithmischen Geometrie(Äquivalenzrelationen zwischen Punktkonfigurationen).

• Effizienzgrenzen für Graphisomorphie- und Homomorphie-Probleme

  Quelle ↗

  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.

Noch keine Publikationen aus OpenAlex zugeordnet.