Given two k-graphs H and F, a perfect F-packing in H is a collection of vertex-disjoint copies of F in H which together cover all the vertices in H. In the case when F is a single edge, a perfect F-packing is simply a perfect matching. For a given fixed F, it is often the case that the decision problem whether an n-vertex k-graph H contains a perfect F-packing is NP-complete. Indeed, if k >= 3, the corresponding problem for perfect matchings is NP-complete [17, 7] whilst if k = 2 the problem is NP-complete in the case when F has a component consisting of at least 3 vertices [14].
展开▼
