α-edge-crossing width and its applications

Abstract

In this thesis, we introduce new graph width parameters, called α-edge-crossing width and edge-crossing width. These are defined in terms of the number of edges crossing a bag of a tree-cut decomposition. We compare them with other known graph parameters. We show that edge-crossing width is equivalent to the tree-partition-width. On the other hand, α-edge-crossing width is a new parameter; tree-cut width and α-edge-crossing width are incomparable, and they both lie between tree-partition-width and edge-cut width. We provide an approximation algorithm that for a given n-vertex graph G, and integers k and α, in time 2^O((α+k) log(α+k))n^2, either outputs a tree-cut decomposition certifying that the α- edge-crossing width of G is at most 2α^2 + 5k or reports the α-edge-crossing width of G is more than k. As applications, we show that for a fixed α, List Coloring and Precoloring Extension are fixed parameter tractable parameterized by α-edge-crossing width. It was known that they are fixed parameter tractable parameterized by edge-cut width. However, they were known to be W[1]-hard parameterized by tree-cut width. We close the complexity gap between these two parameters.