Kombinatorische Strukturen und Algorithmen in symmetrischen Graphen

• Antragsteller: Professor Dr. Martin Skutella, seit 9/2019
• Fachliche Zuordnung: Theoretische Informatik ; Mathematik
• Förderung: Förderung von 2018 bis 2022
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 413902284

Das Hauptziel dieses Projekts ist es, neue theoretische Resultate über Kreise und andere fundamentale Strukturen, wie zum Beispiel Pfade und Matchings, in verschiedenen Familien symmetrischer Graphen zu gewinnen, und die dazugehörigen kombinatorischen Algorithmen zu implementieren. Der Ausgangspunkt unseres Projekts ist eine berühmte Vermutung von Lovász aus den 1970er Jahren, nach der jeder zusammenhängende und knotentransitive Graph einen Hamiltonkreis besitzt, mit fünf bekannten Ausnahmen. Ein knotentransitiver Graph sieht von jedem Knoten betrachtet ‘gleich aus’, und ein Hamiltonkreis ist ein Kreis, der jeden Knoten des Graphen genau einmal besucht. Eines der Ziele dieses Projekts ist es, diverse Spezialfälle von Lovász’ Vermutung in Angriff zu nehmen, die ebenfalls bereits lange offen sind, und für die wir kürzlich signifikante Fortschritte erzielen konnten. Dieser Teil des Projekts ist eine Fortsetzung unserer Arbeiten zur Lösung mehrerer lange offener Probleme auf diesem Gebiet, insbesondere zur berüchtigten Middle-Levels-Vermutung aus den 1980er Jahren. Außerdem werden wir neue Gray-Code-Algorithmen für verschiedene kombinatorische Objekte entwickeln, die für Informatiker interessant sind, wie zum Beispiel Bitfolgen, Permutationen, geometrische Konfigurationen, Posets und Polytope. Diese Probleme zu lösen, erfordert die Kombination und Entwicklung neuer theoretischer Werkzeuge und Techniken aus diversen Teilgebieten, und diese neuen Techniken und Querverbindungen sind für andere Forscher von Interesse. Desweiteren planen wir, alle im Verlauf dieses Projekts entwickelten Algorithmen zu implementieren, und für andere Forscher, Studenten und Lehrpersonen verfügbar zu machen. Dazu wollen wir gemeinsam mit anderen Forschern die Webseite Combinatorial Object Server neu lancieren, die ursprünglich von Frank Ruskey betrieben wurde. Diese Webseite bietet einen einfach zu benutzenden Zugang zum Experimentieren und Herunterladen von Open-Source-Code für verschiedene grundlegende kombinatorische Algorithmen.

• DFG-Verfahren: Sachbeihilfen
• Ehemaliger Antragsteller: Dr. Torsten Mütze, bis 8/2019