A parameterized algorithm for tree-cut width.

The VCLA and WPI will host a talk by EunJung Kim on July 28, 2014.

ABSTRACT

We present a notion called immersion and a related decomposition called the tree-cut decomposition. Immersion is an edge-analogue of topological minor: we request the paths connecting branching vertices to be edge-disjoint, unlike in topological minor, where vertex-disjoint paths connect branching vertices. There has been a rush of attention recently on the study of immersions.

It was shown that graphs are well-quasi-ordered under (weak) immersion containment. The relation between coloring and exclusion of a clique immersion is a favored topic as well. It is known that if a graph has a big tree-cut width, then it contains a big wall as an immersion. In this sense, the tree-cut decomposition plays the role of the tree decomposition in the world of immersions. In this talk, we present 2-approximation for constructing tree-cut decomposition in fpt-time. A min-max type of cut problem is defined as a subproblem in the course of designing the algorithm. Our approximation for tree-cut decomposition is reduced to such a cut problem. The latter problem is shown to be fixed-parameter tractable using randomized contraction technique.