AG 1   Info

AG Audience

English

30 Minutes

Saarbrücken

Wollan has recently introduced the graph parameter tree-cut width, which 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 which are not believed 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 G. On the other hand, we show that List Coloring, Precoloring Extension and Boolean CSP (the latter parameterized by the tree-cut with of the incidence graph) are unlikely to be fixed parameter tractable when parameterized by tree-cut width. This is a joint work with Robert Ganian and Stefan Szeider.

Holger Dell

--email hidden

passcode not visible

logged in users only