E192-01 - Forschungsbereich Algorithms and Complexity
SIAM Journal on Discrete Mathematics
Number of Pages:
immersion; integer linear programming; parameterized complexity; structural parameters; tree-cut width
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-hard and hence unlikely to be FPT when parameterized by tree-cut width.
New Frontiers for Parameterized Complexity: P31336-N35 (FWF Fonds zur Förderung der wissenschaftlichen Forschung (FWF)) Parameterisierte Analyse in der Künstlichen Intelligenz: Y1329-N (FWF Fonds zur Förderung der wissenschaftlichen Forschung (FWF)) Revealing and Utilizing the Hidden Structure for Solving Hard Problems in AI: ICT19-065 (WWTF Wiener Wissenschafts-, Forschu und Technologiefonds)