R. Ganian, Ej Kim, S. Szeider:

"Algorithmic Applications of Tree-Cut Width";

Talk: International Symposium on Mathematical Foundations of Computer Science (MFCS), Milan, Italy; 2015-08-24 - 2015-08-28; in: "Proceedings of the 40th International Symposium Mathematical Foundations of Computer Science 2015", LNCS 9235 (2015), ISBN: 978-3-662-48053-3; 348 - 361.

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 which 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 G. 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.

http://publik.tuwien.ac.at/files/PubDat_247923.pdf

Created from the Publication Database of the Vienna University of Technology.