Combinatorial structures and algorithms in symmetric graphs

• Applicant: Professor Dr. Martin Skutella, since 9/2019
• Subject Area: Theoretical Computer Science ; Mathematics
• Term: from 2018 to 2022
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 413902284

• Final Report Year: 2022

Final Report Abstract

Ziel des Projekts war es, neue theoretische Ergebnisse zu Strukturen und Algorithmen in symmetrischen Graphen zu gewinnen, und neue Querverbindungen zwischen verschiedenen mathematischen Teilgebieten aufzudecken. Viele der ambitionierten Meilensteine des Projekts wurden vollständig erreicht, und außerdem wurden weitreichende neue Forschungsrichtungen und -fragen angestoßen, die Gegenstand laufender Untersuchungen sind. Erwähnenswert sind insbesondere die folgenden Ergebnisse des Projekts: Eine Vermutung von Donald Knuth, die in seinem Buch ‘The Art of Computer Programming Vol. 4A’ als schwierigstes offenes Problem genannt wird, wurde vollständig bewiesen und in einen effizienten Algorithmus umgesetzt. Knuth gratulierte den Autoren zu diesem Erfolg mit den Worten: ‘Congratulations on another milestone!’ (‘Glückwunsch zu einem neuerlichen Meilenstein!’), und einige der in diesem Projekt erzielten Ergebnisse werden in der neuesten Ausgabe von Knuths Buch zitiert. Eine andere lange offene Vermutung, das sogenannte ‘central levels problem’, über Hamiltonkreise in symmetrischen Graphen, wurde vollständig bewiesen. Außerdem wurde eine Vermutung zu Hamiltonkreisen in Knesergraphen für den dünnsten und somit schwierigsten Teilfall gelöst. Um neue Ergebnisse für das Projekt zu erzielen, wurden drei erwähnenswerte Querverbindungen zu Methoden aus verwandten mathematischen Teilgebieten etabliert. Zum einen sind dies symmetrische Kettenzerlegungen, die ursprünglich in der Ordnungstheorie entwickelt wurden, und die nun in einem neuen Zusammenhang Anwendung finden. Außerdem ist dies ein neuartiger Greedy-Algorithmus für die Erzeugung von Basen von Matroiden, die in der kombinatorischen Optimierung eine wichtige Rolle spielen, und wodurch sich zahlreiche neue Perspektiven ergeben. Desweiteren wurde ein neuer Graphenparameter eingeführt, der die Symmetrie eines Graphen bezüglich seiner Hamiltonkreise misst, und damit neue Einsichten in eine alte Vermutung von Lovász aus dem Jahr 1970 ermöglicht. Neben der Lösung lange offener Probleme erzielte das Projekt auch signifikante Fortschritte bei der Entwicklung einer mächtigen und flexiblen Theorie zur systematischen Entwicklung von Algorithmen zur Erzeugung kombinatorischer Objekte mittels Gray-Codes. Dieser neue Ansatz fand bereits zahlreiche Anwendungen und mündete in eine Reihe von bisher fünf Publikationen, in denen die neue Methode erfolgreich auf ganz verschiedene kombinatorische Objekte angewendet wird (dies sind muster-vermeidende Permutationen, Verbandskongruenzen der schwachen Ordnung der symmetrischen Gruppe, Rectangulierungen, Eliminationsbäume, sowie azyklische Orientierungen von Graphen). Ein wesentliches Auszeichnungsmerkmal des neuen Ansatzes liegt darin, dass die Auflistung der Objekte zu einem Spaziergang auf einem zugeordneten hochdimensionalen Polytop korrespondiert, was eine Gütegarantie impliziert, und außerdem neue geometrische Einsichten ermöglicht. Die im Projekt erzielten Resultate wurden in insgesamt 27 Publikationen bei Konferenzen und Journalen veröffentlicht. Dabei gelangen vier aufeinanderfolgende Publikationen bei SODA, der führenden internationalen Konferenz zu Algorithmen, sowie Publikationen im SIAM Journal of Computing, Transactions of the AMS, Journal of the LMS, und im Israel Journal of Mathematics. Außerdem erhielten die Autoren den Best Paper Award für eine Publikation in der Konferenz ‘Mathematical Foundations of Computer Science (MFCS)’ 2022. Viele der in diesem Projekt entwickelten Algorithmen wurden in C++ implementiert und für die Allgemeinheit auf dem Combinatorial Object Server öffentlich zugänglich gemacht.

Publications

• Sparse Kneser graphs are Hamiltonian. Journal of the London Mathematical Society, 103(4), 1253-1275.
  Mütze, Torsten; Nummenpalo, Jerri & Walczak, Bartosz
  
• Combinatorial generation via permutation languages. II. Lattice congruences. Israel Journal of Mathematics, 244(1), 359-417.
  Hoang, Hung P. & Mütze, Torsten
  
• Combinatorial generation via permutation languages. I. Fundamentals. Transactions of the American Mathematical Society, 375(04), 2255-2291.
  Hartung, Elizabeth; Hoang, Hung P.; Mütze, Torsten & Williams, Aaron
  
• Combinatorial Generation via Permutation Languages. III. Rectangulations. Discrete & Computational Geometry, 70(1), 51-122.
  Merino, Arturo & Mütze, Torsten
  
• Efficient generation of elimination trees and graph associahedra. Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2128-2140. Society for Industrial and Applied Mathematics.
  Cardinal, Jean; Merino, Arturo & Mütze, Torsten
  
• Gray codes and symmetric chains. Journal of Combinatorial Theory, Series B, 153, 31-60.
  Gregor, Petr; Jäger, Sven; Mütze, Torsten; Sawada, Joe & Wille, Kaja
  
• On a Combinatorial Generation Problem of Knuth. SIAM Journal on Computing, 51(3), 379-423.
  Merino, Arturo; Mička, Ondřej & Mütze, Torsten
  
• On the central levels problem. Journal of Combinatorial Theory, Series B, 160, 163-205.
  Gregor, Petr; Mička, Ondřej & Mütze, Torsten
  
• Zigzagging through acyclic orientations of chordal graphs and hypergraphs. Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 3029-3042. Society for Industrial and Applied Mathematics.
  Cardinal, Jean; Hoang, Hung P.; Merino, Arturo & Mütze, Torsten