Approximation algorithms and hardness results for the clique packing problem

Abstract: For a fixed family of graphs, an -packing in a graph is a set of pairwise vertex-disjoint subgraphs of , each isomorphic to an element of . Finding an -packing that maximizes the number of covered edges is a natural generalization of the maximum matching problem, which is just . In this paper we provide new approximation algorithms and hardness results for the -packing problem where . We show that already for the -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 . For we obtain better approximations. For we obtain a simple -approximation, achieving a known ratio that follows from a more involved algorithm of Halldórsson. For , we obtain a -approximation, and for we obtain a -approximation. [Copyright &y& Elsevier]