Minimum constellation covers: hardness, approximability and polynomial cases

This paper considers two graph covering problems, the Minimum Constellation Cover (CC) and the Minimum k-Split Constellation Cover (k-SCC). The input of these problems consists on a graph $$G=\left( V,E\right) $$ G = V , E and a set $${\mathcal {C}}$$ C of stars of G, and the output is a minimum cardinality set of stars C, such that any two different stars of C are edge-disjoint and the union of the stars of C covers all edges of G. For CC, the set C must be compound by edges of G or stars of $${\mathcal {C}}$$ C while, for k-SCC, an integer k is given and the elements of C must be k-stars obtained by splitting stars of $${\mathcal {C}}$$ C . This work proves that unless $$P=NP$$ P = N P , CC does not admit polynomial time $$\left| {\mathcal {C}}\right| ^{{\mathcal {O}}\left( 1\right) }$$ C O 1 -approximation algorithms and k-SCC cannot be $$\left( \left( 1-\epsilon \right) \ln \left| E\right| \right) $$ 1 - ϵ ln E -approximated in polynomial time, for any $$\epsilon >0$$ ϵ > 0 . Additionally, approximation ratios are given for the worst feasible solutions of the problems and, for k-SCC, polynomial time approximation algorithms are proposed, achieving a $$\left( \ln \left| E\right| -\ln \ln \left| E\right| +\varTheta \left( 1\right) \right) $$ ln E - ln ln E + Θ 1 approximation ratio. Also, polynomial time algorithms are presented for special classes of graphs that include bounded degree trees and cacti.