[Back]


Talks and Poster Presentations (with Proceedings-Entry):

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.



English 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. 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.


Electronic version of the publication:
http://publik.tuwien.ac.at/files/PubDat_247923.pdf


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