Zerlegungen, Tangles und Cluster

• Antragsteller: Professor Dr. Martin Grohe
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2019 bis 2024
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 414230410

• Erstellungsjahr: 2025

Zusammenfassung der Projektergebnisse

Baumzerlegungen, die beschreiben, wie ein Graph in weitgehend unabhängige Teile zerlegt werden kann, sind zu einem Standardwerkzeug bei der Entwicklung effizienter Algorithmen in vielen Bereichen der Informatik geworden. Die strukturelle Graphentheorie bietet mehrere duale Konzepte zu Baumzerlegungen an, die intuitiv als Beschreibung stark zusammenh ängender Regionen in Graphen betrachtet werden können. Unter diesen Konzepten sind sogenannte Tangles wohl das wichtigeste. Eine zweite interessante duale Charakterisierung ergibt sich durch Suchspiele auf Graphen, die in ihrer bekanntesten Form auch als ”Cops-and-Robber”-Spiele bezeichnet werden. Der Hauptbeitrag dieses Projekts bestand darin, eine enge Verbindung zwischen Tangles und Clusterings herzustellen. Die Beobachtung einer interessanten konzeptionellen ¨ Ahnlichkeit zwischen Tangles und Cluster geht auf Diestel und Whittle (2016) zurück und war eine der Hauptmotivationen für dieses Projekt. Um dies in einen mathematischen Satz zu überführen, war es entscheidend, den Begriff der Konnektivitätsfunktion auf einem Datensatz zu erweitern und Konnektivitätsfunktionen zu betrachten, die eine Eigenschaft besitzen, die wir Max-Submodularität nennen. Wir konnten zeigen, dass Tangles, die aus max-submodularen Konnektivit ätsfunktionen abgeleitet werden, in direkter Korrespondenz zu hierarchischen Clusterings des Datensatzes stehen. Um die Verbindung zwischen Tangles und Clustern auch in einem praktisch relevanten Kontext zu untersuchen, haben wir die Tangles von Datensätze, die durch Gaussian Mixtures erzeugt wurden, analysiert. Ein weiterer Beitrag dieses Projekts betrifft Suchspiele für Graphzerlegungen, die Breite und Tiefe gleichzeitig einschränken. Schlieslich haben wir auch zur Untersuchung einer neuartigen Form der Zerlegung beigetragen,den sogenannten radialen Zerlegungen, die nicht mehr unbedingt baumartig sein müssen.

Projektbezogene Publikationen (Auswahl)

• “Tangles and Single Linkage Hierarchical Clustering”. In: 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019, August 26-30, 2019, Aachen, Germany. Ed. by P. Rossmanith, P. Heggernes, and J. Katoen. Vol. 138. LIPIcs. Selected as Best Student Paper. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, 38:1–38:12
  E. Fluck
  
• A structural duality for path-decompositions into parts of small radius
  S. Albrechtsen, R. Diestel, A.-K. Elm, E. Fluck, R. W. Jacobs, P. Knappe & P. Wollan
  
• Tangles and Hierarchical Clustering. SIAM Journal on Discrete Mathematics, 38(1), 75-92.
  Fluck, Eva
  
• Untangling Gaussian Mixtures
  E. Fluck, S. Kiefer & C. Standke
  
• “Going Deep and Going Wide: Counting Logic and Homomorphism Indistinguishability over Graphs of Bounded Treedepth and Treewidth”. In: 32nd EACSL Annual Conference on Computer Science Logic, CSL 2024, February 19-23, 2024, Naples, Italy. Ed. by A. Murano and A. Silva. Vol. 288. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, 27:1–27:17
  E. Fluck, T. Seppelt & G. L. Spitzer
  
• “Graph Decompositions – A Study on Decompositions of Graphs and their Application to Logic and Data Science”. PhD thesis. RWTH Aachen University, 2024
  E. Fluck
  
• “Monotonicity of the Cops and Robber Game for Bounded Depth Treewidth”. In: 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Ed. by R. Královič and A. Kučera. Vol. 306. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024, 6:1–6:18. isbn: 978-3-95977-335-5.
  Adler & E. Fluck