Star Covers and Star Partitions of Cographs and Butterfly-free Graphs

A graph that is isomorphic to \(K_{1,r}\) for some \(r\ge 0\) is called a star. For a graph \(G = (V, E)\) , any subset S of its vertex set V is called a star of G if the subgraph induced by S is a star. A collection \(\mathcal {C} = \{V_1, \ldots , V_k\}\) of stars in G is called a star cover of G if \(V_1\cup \ldots \cup V_k = V\) . A star cover \(\mathcal {C}\) of G is called a star partition of G if it is also a partition of V. Given a graph G, the problem Star Cover asks for a star cover of G of minimum size. Given a graph G, the problem Star Partition asks for a star partition of G of minimum size. Both the problems are NP-hard even for bipartite graphs [24]. In this paper, we obtain exact \(O(n^2)\) time algorithms for both Star Cover and Star Partition on \((C_4,P_4)\) -free graphs and on \((2K_2,P_4)\) -free graphs. We also prove that Star Cover and Star Partition are polynomially equivalent, up to the optimum value, for butterfly-free graphs and present an \(O(n^{14})\) time \(O(\log n)\) -approximation algorithm for these equivalent problems on butterfly-free graphs. We also obtain \(O(\log n)\) -approximation algorithms for Star Cover on hereditary graph classes.