2023/02/09 by Yeonsu Chang, Chang, Yeonsu, O‐joung Kwon +3
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.2302.04624
openalex publication_date 2023/02/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We introduce 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. They are motivated by edge-cut width, recently introduced by Brand et al. (WG 2022). We show that edge-crossing width is equivalent to the known parameter 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 algorithm that, for a given n-vertex graph G and integers k and α, in time 2O((α+k)log (α+k))n2 either outputs a tree-cut decomposition certifying that the α-edge-crossing width of G is at most 2α2+5k or confirms that the α-edge-crossing width of G is more than k. As applications, for every fixed α, we obtain FPT algorithms for the List Coloring and Precoloring Extension problems parameterized by α-edge-crossing width. They were known to be W[1]-hard parameterized by tree-partition-width, and FPT parameterized by edge-cut width, and we close the complexity gap between these two parameters.