Neue algorithmische Schranken für Isomorphieprobleme über Graphen und andere algebraische Strukturen

• Antragsteller: Professor Dr. Jacobo Torán
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2013 bis 2018
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 225911997

Isomorphieprobleme spielen in theoretischer als auch praktischer, algorithmischer Sichteine wichtige Rolle. Eine exakte Klassifikation der Komplexität für die Isomorphie vonGraphen als auch anderer algebraischer Strukturen ist seit Jahrzehnten ein offenesProblem. Bekannte Verfahren und Komplexitätsklassen scheinen ungeeignet zu sein um dieseFragen zu beantworten. Einige in der ersten Hälfte des Projektes erzielten Resultateverbessern das Verständnis der Komplexität von Isomorphieproblemen durch neue Ansätze imBereich der parametrisierten Algorithmen sowie der Schaltkreistheorie.In der zweiten Hälfte des Projektes möchten wir diese Arbeit fortführen. Zum einenmöchten wir weitere Methoden, welche wir bereits in unserem ersten Antrag beschriebenhaben, anwenden. Hierzu gehören parametrisierte Algorithmen für Hypergraph-Isomorphiesowie eingeschränkte Varianten der Graphenisomorphie. Zum anderen möchten wirIsomorphieprobleme aus zwei neuen Richtungen angehen: Variante des Isomorphie-Problems,welche durch besonders kleine Kodierungen wie Schaltkreise entstehen, als auchBeziehungen zwischen Graphenisomorphie und Beweiskomplexität.

• DFG-Verfahren: Sachbeihilfen