Approximation algorithms and hardness results for the clique packing problem

• Published in: Discrete Applied Mathematics 2009-04, Vol.157 (7), p.1396-1406
• Main Authors: Chataigner, F., Manić, G., Wakabayashi, Y., Yuster, R.
• Format: Article
• Language: English
• Subjects: Algorithmics. Computability. Computer arithmetics; Applied sciences; Approximation algorithms; apx-hardness; Clique; Combinatorics; Combinatorics. Ordered structures; Computer science; control theory; systems; Designs and configurations; Exact sciences and technology; Information retrieval. Graph; Mathematics; Packing; Sciences and techniques of general use; Theoretical computing; Triangle
• ISSN: 0166-218X; 1872-6771
• DOI: 10.1016/j.dam.2008.10.017

For a fixed family F of graphs, an F -packing in 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 = { K 2 } . In this paper we provide new approximation algorithms and hardness results for the K r -packing problem where K r = { K 2 , K 3 , … , K r } . We show that already for r = 3 the K r -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 r . For r = 3 , 4 , 5 we obtain better approximations. For r = 3 we obtain a simple 3 / 2 -approximation, achieving a known ratio that follows from a more involved algorithm of Halldórsson. For r = 4 , we obtain a ( 3 / 2 + ϵ ) -approximation, and for r = 5 we obtain a ( 25 / 14 + ϵ ) -approximation.