KAIST Discrete Math Seminar

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. 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 present a 2-approximation fpt-algorithm for the problem of deciding whether the tree-cut width is at most k: that is, given a graph G and a positive integer k, the algorithm correctly decides in time 2^{O(k2 log k)}·n⁵ log n that the tree-cut width of G is strictly bigger than k, or returns a tree-cut decomposition whose width is at most 2k. Moreover, we develop the notion of nice tree-cut decompositions and show that any tree-cut decomposition can be transformed into a nice one in polynomial time. Based on this notion, we introduce a general three-stage dynamic framework for the design of FPT algorithms on nice tree-cut decompositions and apply it to several classic problems.
This talk is based on two recent works with Robert Ganian, Stefan Szeider, Sang-il Oum, Christophe Paul, Ignasi Sau and Dimitrios Thilikos.