Packing subgraphs in a graph

• Gordana Manić USP
• Yoshiko Wakabayashi USP

Abstract

For a fixed family F of graphs, an F-packing of a graph G is a set of pairwise vertex-disjoint (or edge-disjoint) subgraphs of G, each isomorphic to an element of F. We focus on the algorithmic aspects of the problem of finding an F-packing that maximizes the number of covered edges. We present results for F = {K₃} and F = {K₂, K₃}. For F = {K₃}, we present approximation algorithms for bounded degree graphs, improving the ratio known for the general case. When F = {K₂, K₃}, we study the vertex-disjoint version. We prove that this problem is APX-hard even on graphs with maximum degree 4. Furthermore, we present a (3/2+ε)-approximation algorithm for arbitrary graphs, and a 1.4-approximation algorithm for graphs with maximum degree 4.

References

Baker, B. S. (1994). Approximation algorithms for NP-complete problems on planar graphs. J. Assoc. Comput. Mach., 41(1):153–180.

Caprara, A. and Rizzi, R. (2002). Packing triangles in bounded degree graphs. Inform. Process. Lett., 84(4):175–180.

Chataigner, F., Manić, G., Wakabayashi, Y., and Yuster, R. (2007). Approximation algorithms and hardness results for the clique packing problem. Extended abstract accepted to EuroComb 2007, to appear in Electronic Notes in Discrete Mathematics (full paper submitted to a journal).

Chlebík, M. and Chlebíková, J. (2004). On approximability of the independent set problem for low degree graphs. In Lecture Notes in Computer Science 3104, pages 47–56. Springer.

Guruswami, V., Pandu Rangan, C., Chang, M. S., Chang, G. J., and Wong, C. K. (2001). The K-, -packing problem. Computing, 66(1):79–89.

Hell, P. and Kirkpatrick, D. (1983). On the complexity of general graph factor problems. SIAM J. Comput., 12(3):601–609.

Hell, P. and Kirkpatrick, D. (1984). Packings by cliques and by finite families of graphs. Discrete Math., 49:45–59.

Holyer, I. (1981). The NP-completeness of some edge-partition problems. SIAM J. Comput., 10(4):713–717.

Hurkens, C. A. J. and Schrijver, A. (1989). On the size of systems of sets every t of which have an SDR, with an application to the worst-case ratio of heuristics for packing problems. SIAM J. Discrete Math., 2(1):68–72.

Karp, R. M. (1975). On the computational complexity of combinatorial problems. Networks, 5(1):45–68.

Looges, P. J. and Olariu, S. (1993). Optimal greedy algorithms for indifference graphs. Comput. Math. Appl., 25(7):15–25.

Manić, G. and Wakabayashi, Y. (2005). Packing triangles in low degree graphs and indifference graphs. In Discrete Math. and Theoretical Computer Science, volume AE – EuroComb 2005 special volume, pages 251–256 (full paper submitted to a journal).