On the kernelization of split graph problems

A split graph is a graph whose vertices can be partitioned into a clique and an independent set. We study numerous problems on split graphs, namely the k-Vertex-Disjoint Paths, k-Cycle, k-Path and k-ℓ-Stable Set problems. In the k-Vertex-Disjoint Paths problem, we are given a graph and k terminal pairs of vertices, and are asked whether there is a set of k vertex-disjoint paths linking these terminal pairs, respectively. In the k-Cycle/k-Path problem, we are given a graph and are asked whether there is a path/cycle of length k. The k-ℓ-Stable Set problem takes a graph and an integer k as input, and asks whether the graph has a subset of k vertices such that the distance between every two vertices in the subset is at least ℓ+1. It is known that all the above problems are NP-complete on split graphs. We derive a 4k-vertex kernel for the k-Vertex-Disjoint Paths problem and an O(k2)-vertex kernel for both the k-Path problem and the k-Cycle problem. Concerning the k-ℓ-Stable Set problem, for ℓ=1 or ℓ≥3, the problem is polynomial-time solvable on split graphs. For ℓ=2, we prove that the k-ℓ-Stable Set problem is W[1]-complete on split graphs, with respect to k. However, if the given split graph contains no K1,r as an induced subgraph, and every vertex in the independent set of the split graph has degree at most d, we derive a linear vertex kernel for the k-2-Stable Set problem, where both r and d are constants.