Decompositions, Tangles, and Clusters

• Applicant: Professor Dr. Martin Grohe
• Subject Area: Theoretical Computer Science
• Term: from 2019 to 2024
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 414230410

Tree decompositions, describing how a graph can be cut into largely independent pieces, have become a standard tool in the design of algorithms with applications in many different areas of Computer science. Structural graph theory offers various concepts "dual" to tree decompositions. Intuitively, these can be viewed as describing highly connected regions in graphs. Among them, arguably, tangles are the most important. While far less prominent than tree decompositions, tangles and related concepts such as brambles and well-linked setshave proved useful in several computer science applications, and we feel they have a considerable untapped potential. A largely unexplored idea, first formulated by Diestel and Whittle (2016) in the context of image segmentation, is to use tangles in clustering applications.It is the goal of this proposal to generalise the theory of decompositions and tangles towards new applications in clustering and constraint satisfaction. Technically, this requires an extension of the theory from integer-valued to real-valued connectivity functionsand an extension to new, hybrid decompositions. One important focus of this proposal will be to strengthen the currently underdeveloped algorithmic theory of tangles.

• DFG Programme: Research Grants