Approximation algorithms and hardness results for the clique packing problem

For a fixed family FF of graphs, an FF-packing in a graph GG is a set of pairwise vertex-disjoint subgraphs of GG, each isomorphic to an element of FF. Finding an FF-packing that maximizes the number of covered edges is a natural generalization of the maximum matching problem, which is just F={K2}F={K2}. In this paper we provide new approximation algorithms and hardness results for the KrKr-packing problem where Kr={K2,K3,…,Kr}Kr={K2,K3,…,Kr}.We show that already for r=3r=3 the KrKr-packing problem is APX-complete, and, in fact, we show that it remains so even for graphs with maximum degree 4. On the positive side, we give an approximation algorithm with approximation ratio at most 2 for every   fixed rr. For r=3,4,5r=3,4,5 we obtain better approximations. For r=3r=3 we obtain a simple  3/23/2-approximation, achieving a known ratio that follows from a more involved algorithm of Halldórsson. For r=4r=4, we obtain a (3/2+ϵ)(3/2+ϵ)-approximation, and for r=5r=5 we obtain a (25/14+ϵ)(25/14+ϵ)-approximation.