Effizienzgrenzen für das Graphisomorphie-Problem


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 der
Angewandten 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).

Projektleitung
Verbitsky, Oleg Dr. (Details) (Algorithmen und Komplexität II)

Laufzeit
Projektstart: 08/2011
Projektende: 05/2015

Zuletzt aktualisiert 2020-11-03 um 23:16