Decompositions, Tangles, and Clusters

树分解描述了如何将一个图分割成基本上独立的部分，已经成为设计算法的标准工具，在计算机科学的许多不同领域都有应用。结构图理论为树的分解提供了各种“对偶”概念。直观地说，这些可以被视为在图形中描述高度连通的区域。可以说，在这些问题中，纠缠是最重要的。虽然远不如树分解那么突出，但缠结和相关概念，如荆棘和链接良好的集合，已被证明在几个计算机科学应用中很有用，我们认为它们有相当大的未开发潜力。一个很大程度上未被探索的想法，首先是由Diestel和Whitte(2016)在图像分割的背景下提出的，即在聚类应用中使用纠缠。该提议的目标是将分解和纠缠理论推广到聚类和约束满足的新应用中。从技术上讲，这需要将理论从整数值连通性函数扩展到实数值连通性函数，并扩展到新的混合分解。这项提议的一个重要焦点将是加强目前不发达的纠缠算法理论。

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.