Current Challenges in Isomorphism Testing and Graph Canonization

Ob das Problem, die Isomorphie zweier gegebener Graphen zu entscheiden, in Polynomialzeit lösbar ist, ist eine der wichtigsten offenen Fragen der Theoretischen Informatik. In einer stärkeren Variante des Problems ist ein (einzelner) Eingabegraph in eine kanonische Form zu überführen, sodass isomorphen Eingabegraphen der gleiche Kanon zugeordnet wird. Die Herausforderung, die Komplexität von Graphenisomorphie und -kanonisierung zu bestimmen, ist durch den kürzlichen Durchbruch Babais noch gewachsen, der einen Algorithmus vorgestellt hat, der diese Probleme in subexponentieller Zeit löst. Als unser Hauptziel möchten wir zum Verständnis beitragen, ob eine superpolynomielle Laufzeit inhärent für Isomorphie und Kanonisierung ist oder ob sie nur durch die Grenzen aktueller Methoden bedingt ist. Wir konzentrieren uns auf Paritionierungstechniken, die einen Eckpfeiler von Babais Algorithmus bilden, und deren Potential noch nicht in vollem Maße erschlossen scheint. Dabei berücksichtigen wir auch Methoden der Linearen Programmierung - insbesondere Techniken und Konzepte, die auf Ganzzahligkeitseigenschaften des Polytops der fraktionalen Automorphismen eines Graphen beruhen. Dieser Ansatz wurde in den späten Achtzigern von Tinhofer erarbeitet und verdient eine genauere Betrachtung, da er zusammen mit einer zugehörigen Prozedur zur Individualisierung und Verfeinerung vielversprechende Werkzeuge für die Kanonisierung hochsymmetrischer regulärer Graphen bietet. Andere Teilthemen des Projekts sind platzeffiziente Isomorphiealgorithmen und die Effizienz kombinatorischer Partitionierungsmethoden für das Gruppenisomorphie-Problem, dessen Komplexitätsstatus als Hürde für das Lösen des Graphenisomorphieproblems in Polynomialzeit gilt.