Notice
This item was automatically migrated from a legacy system. It's data has not been checked and might not meet the quality criteria of the present system.
Ganian, R., Kim, E. J., & Szeider, S. (2015). Algorithmic Applications of Tree-Cut Width. In Proceedings of the 40th International Symposium Mathematical Foundations of Computer Science 2015 (pp. 348–361). http://hdl.handle.net/20.500.12708/56451
E192-01 - Forschungsbereich Algorithms and Complexity
-
Published in:
Proceedings of the 40th International Symposium Mathematical Foundations of Computer Science 2015
-
Date (published):
2015
-
Event name:
International Symposium on Mathematical Foundations of Computer Science (MFCS)
-
Event date:
26-Aug-2013 - 30-Aug-2013
-
Event place:
Klosterneuburg, Austria, Austria
-
Number of Pages:
14
-
Peer reviewed:
Yes
-
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 pot...
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.