The recently introduced graph parameter tree-cut width plays a similar role with respect to immersions as the graph parameter treewidth plays with respect to minors. In this paper, we provide the first algorithmic applications of tree-cut width to hard combinatorial problems. Tree-cut width is known to be lower-bounded by a function of treewidth, but it can be much larger and hence has the potential to facilitate the efficient solution of problems that are not known to be fixed-parameter tractable (FPT) when parameterized by treewidth. We introduce the notion of nice tree-cut decompositions and provide FPT algorithms for the showcase problems Capacitated Vertex Cover, Capacitated Dominating Set, and Imbalance parameterized by the tree-cut width of an input graph. On the other hand, we show that List Coloring, Precoloring Extension, and Boolean CSP (the latter parameterized by the tree-cut width of the incidence graph) are W[1]-hard and hence unlikely to be fixed-parameter tractable when parameterized by tree-cut width.

翻译：最近引入的图形参数树切宽度与图形参数树枝宽度对未成年人的作用相似。 在本文中, 我们提供树切宽度的第一个算法应用到硬组合问题。 已知树切宽度受树线的函数影响较小, 但它可能大得多, 因此有可能促进有效解决在树宽参数下参数化时不为人所知的固定参数可移动的问题。 我们引入了良好的树切分解作用的概念, 并为显示显示的电动电动层覆盖、 能力化引力集和因输入图的树切宽度而设定的平衡度问题提供 FPT 算法。 另一方面, 我们显示列表、 预色扩展和 Boolean CSP (后一个按事件图的树切宽度参数化) 是W[ 1] 硬的, 因此在按树切宽度参数化时不可能固定参数化。