Algorithmic applications of tree-cut width

Abstract

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. Treecut 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 fixedparameter tractable (FPT) when parameterized by treewidth. We introduce the notion of nice treecut 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 last parameterized by the tree-cut width of the incidence graph) are W[1]-hard and hence unlikely to be FPT when parameterized by tree-cut width.