2013/10/22 by Leizhen Cai, Cai, Leizhen, Chengwei Guo +1
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1310.5786
14 pages, 4 figures
arxiv created 2013/10/22 · openalex publication_date 2013/10/22 · arxiv updated 2013/10/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the parameterized complexity of Split Contraction and Threshold Contraction. In these problems we are given a graph G and an integer k and asked whether G can be modified into a split graph or a threshold graph, respectively, by contracting at most k edges. We present an FPT algorithm for Split Contraction, and prove that Threshold Contraction on split graphs, i.e., contracting an input split graph to a threshold graph, is FPT when parameterized by the number of contractions. To give a complete picture, we show that these two problems admit no polynomial kernels unless NP⊆ coNP/poly.