Approximation algorithms and hardness results for the clique packing problem

For a fixed family F of graphs, an F-packing of a graph G is a set of pairwise vertex-disjoint subgraphs of G, each isomorphic to an element of F. Finding an F-packing that maximizes the number of covered edges is a natural generalization of the maximum matching problem, which is just F={K2}. We provide new approximation algorithms and hardness results for the Kr-packing problem where Kr={K2,K3,…,Kr}. We prove that already for r=3 the Kr-packing problem is APX-hard, and 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 r. For r=3,4,5 we obtain better approximations. For r=3 we obtain a simple 3/2 approximation, matching a known ratio that follows from a more complicated algorithm of Halldórsson. For r=4 and r=5, we obtain the ratios 3/2+ϵ and 25/14+ϵ, respectively.