On the Complexity of General Graph Factor Problems
David G. Kirkpatrick, Pavol Hell · SIAM Journal on Computing · 1983
For arbitrary graphs G and H, a G-factor of H is a spanning subgraph of G composed of disjoint copies of G. G-factors are natural generalizations of 1-factors (or perfect matchings), in which G replaces the complete graph on two vertices. Our results show that the perfect matching problem is essentially the only instance of the G-factor problem that is likely to admit a polynomial time bounded solution. Specifically, if G has any component with three or more vertices, then the existence question for G-factors is NP-complete. (In all other cases the question can be resolved in polynomial time.) The notion of a G-factor suggests a natural generalization where G is replaced by an arbitrary family of graphs. This generalization gives rise not only to further NP-completeness results but also to new polynomial algorithms and duality theorems extending results of the traditional theory of matching. An indication of the nature and scope of these new results is presented.