Packings by cliques and by finite families of graphs (Q1068852)

If F is a family of connected graphs and G is a graph, then an F-packing of G is a subgraph of G each component of which belongs to F. This paper contains a polynomially bounded algorithm for finding an F-packing of G which as many vertices as possible when F contains \(K_ 2\) and all other graphs in F are hypomatchable, i.e., the deletion of any vertex leaves a graph with a perfect matching. If F does not contain \(K_ 2\), then the problem of finding an F-packing with as many vertices as possible is often NP-complete. This is shown to be the case when F consists of complete graphs of order at least 3 or when F consists of cycles of length at least 6.