On Star Partition of Split Graphs

A graph that is isomorphic to \(K_{1,r}\) for some \(r\ge 0\) is called a star. A partition \(\{V_1, \ldots , V_k\}\) of the vertex set of a graph G into k sets is called a star partition of G of size k if each set in the partition induces a star. The minimum k for which a graph G admits a star partition of size k is called the star partition number of G and is denoted by sp(G). Given a graph G, the problem Min Star Partition asks for a star partition of G of minimum size. Given a graph G and a positive integer k, its decision version Star Partition asks whether \(sp(G) \le k\) . Star Partition is NP-complete for many natural graph classes [25]. In particular, it is NP-complete for \(K_{1,5}\) -free split graphs. In this paper, we study the star partition problems on split graphs, with a special focus on the degrees of vertices in the independent part. We call a split graph (a) an r-split graph if each vertex in the independent part has degree r and (b) an \((r_1, \ldots , r_k)\) -split graph if each vertex in the independent part has degree equal to one of \(r_1, \ldots , r_k\) . We obtain the following NP-completeness results: (1) Star Partition is NP-complete even for \(K_{1,5}\) -free 2-split graphs. (2) Deciding whether \(sp(G) = \lceil \omega (G)/2\rceil \) is NP-complete even for \(K_{1,6}\) -free 2-split graph ( \(sp(G) \ge \lceil \omega (G)/2\rceil \) for any graph G). (3) Star Partition is NP-complete even for (1, r)-split graphs ( \(r\ge 2\) and is fixed). We obtain the following fixed parameter (in)tractability results (in each case, k stands for the parameter) (1) Given any connected split graph G and an integer \(k \ge 1\) , deciding whether \(sp(G) \le k\) is fixed parameter tractable and has an \(O((2k)^{2k+1}n)\) time algorithm. (2) Given a graph G and an integer \(k \ge 0\) , deciding whether \(sp(G) \le \lceil \omega (G)/2 \rceil + k\) is para-NP-hard even when restricted to either (a) \(K_{1,6}\) -free (0, 2)-split graphs or (b) \(K_{1,6}\) -free (0, 1, 3)-split graphs. (3) Given a graph G and an integer \(k\ge 0\) , the problem of deciding whether \(sp(G) \le \omega (G) - k\) is W[1]-hard even for (1, 2)-split graphs and lies in W[3] for connected split graphs ( \(sp(G) \le \omega (G)\) for any connected split graph G). We also obtain the following polynomial time algorithms: (1) 3/2-approximation algorithms for several subclasses of 2-split graphs. (2) A linear time algorithm for (0, 1)-split graphs; in particular, for any 1-split graph G, we prove that \(sp(G) = \max (\lceil \omega (G)/2 \rceil , \alpha (G^2))\) . Most of these results are obtained by an elegant framework that we have developed for the study of star partition on split graphs. Using this, we also obtain a simple characterization for any connected split graph G having \(sp(G) = \omega (G)\) .