论文标题
边缘宽度：基于边缘切割的算法驱动的树宽的类似物
Edge-Cut Width: An Algorithmically Driven Analogue of Treewidth Based on Edge Cuts
论文作者
论文摘要
分解参数（例如树宽）通常用于获得NP-HARD图问题的固定参数算法。对于通过树宽参数化的W [1] hard的问题，一种自然的选择是使用基于边缘切割而不是顶点分离器的合适的树宽类似物。尽管树木宽度的宽度被认为是对边缘切割的树宽的类似物，但其算法应用通常会导致令人失望的结果：在十二个问题中，人们希望通过固定参数的障碍性参数为基于边缘的teepogue of tree-width的类似物，表明了八个的类似物。 作为我们的主要贡献，我们开发了一种基于边缘的类似于树宽的类似物，称为边缘切割宽度。直观地，基于测量循环的密度穿过图形的一棵树的密度。它的好处不仅包括一个相对简单的定义，而且主要是它具有有趣的算法属性：它可以通过固定参数算法计算，并且会为所有上述树木切开宽度无法做到的问题产生固定参数算法。
Decompositional parameters such as treewidth are commonly used to obtain fixed-parameter algorithms for NP-hard graph problems. For problems that are W[1]-hard parameterized by treewidth, a natural alternative would be to use a suitable analogue of treewidth that is based on edge cuts instead of vertex separators. While tree-cut width has been coined as such an analogue of treewidth for edge cuts, its algorithmic applications have often led to disappointing results: out of twelve problems where one would hope for fixed-parameter tractability parameterized by an edge-cut based analogue to treewidth, eight were shown to be W[1]-hard parameterized by tree-cut width. As our main contribution, we develop an edge-cut based analogue to treewidth called edge-cut width. Edge-cut width is, intuitively, based on measuring the density of cycles passing through a spanning tree of the graph. Its benefits include not only a comparatively simple definition, but mainly that it has interesting algorithmic properties: it can be computed by a fixed-parameter algorithm, and it yields fixed-parameter algorithms for all the aforementioned problems where tree-cut width failed to do so.
