Tree-cut width is a parameter that has been introduced as an attempt to obtain an analogue of treewidth for edge cuts. Unfortunately, in spite of its desirable structural properties, it turned out that tree-cut width falls short as an edge-cut based alternative to treewidth in algorithmic aspects. This has led to the very recent introduction of a simple edge-based parameter called edge-cut width [WG 2022], which has precisely the algorithmic applications one would expect from an analogue of treewidth for edge cuts, but does not have the desired structural properties. In this paper, we study a variant of tree-cut width obtained by changing the threshold for so-called thin nodes in tree-cut decompositions from 2 to 1. We show that this "slim tree-cut width" satisfies all the requirements of an edge-cut based analogue of treewidth, both structural and algorithmic, while being less restrictive than edge-cut width. Our results also include an alternative characterization of slim tree-cut width via an easy-to-use spanning-tree decomposition akin to the one used for edge-cut width, a characterization of slim tree-cut width in terms of forbidden immersions as well as approximation algorithm for computing the parameter.
翻译:树枝宽度是一个参数,它被引入,试图获得树枝边切的相似值。 不幸的是,尽管其结构属性是可取的,但结果显示,树枝宽度作为在算法方面树枝宽度的边切替代物,不足以替代树枝边切宽度。这导致最近引入了一个简单的边切参数,称为边切宽度[WG 20222],精确的算法应用程序可以从树枝边切的相似值获得,但不具备理想的结构属性。在本文中,我们研究了通过将树切分解的所谓瘦结点的阈值从2改为1而获得的树切宽度变量。我们表明,这种“树切宽度”满足了基于边切的边切类似值的所有要求,既包括结构宽度,也包括算法,但比边切宽度要少。我们的结果还包括通过易于使用的横切树枝宽度脱色特性,将树枝宽度的阈值定位与用来进行边切的底质定度的底深度,作为树底定度的底定度的底线的精确度的精确度的定值。