Decompositions, Tangles, and Clusters
Final Report Abstract
Tree decompositions, which describe how a graph can be cut into largely independent pieces, have become a standard tool in designing algorithms with applications in many different areas of computer science. Structural graph theory offers various dual concepts to tree decompositions. Intuitively, these can be viewed as describing highly connected regions in graphs. Among them, arguably, tangles are the most important. A second interesting dual characterisation can be given via search games on graphs, which are also called Cops-an-Robber games in their most popular form. The main contribution of this project was to establish a close connection between tangles and clustering. The observation of an interesting conceptual similarity between tangles and clusters goes back to Diestel and Whittle (2016) and was one of the main motivations for this project. To turn this into a mathematical theorem, a crucial idea was to relax the notion of connectivity function on a dataset and consider connectivity functions that have a property we call max-submodularity. Then, we proved that tangles derived from max-submodular connectivity functions are in one-to-one correspondence with the hierarchical clusterings of the dataset. Transferring the connection between tangles and clusterings into a more practical direction, we studied the tangles of datasets generated by mixtures of Gaussian distributions. Another contribution we made in this project concerns search games for graph decompositions that simultaneously restrict width and depth. Finally, we also contributed to investigating a novel form of decomposition, so-called radial decompositions, which drop the requirement of decompositions being tree-shaped.
Publications
-
“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
