# The ICICS/CS Reading Room

## UBC CS TR-81-07 Summary

- No on-line copy of this technical report is available.

- On the Complexity of General Graph Factor Problems, August 1981 David G. Kirkpatrick and P. Hell
For arbitrary graphs G and H, a G-factor of H is a spanning
subgraph of H composed of disjoint copies of G. G-factors are
natural generalizations of l-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.)
.br
The notion of a G-factor is further generalized by replacing
G by an arbitrary family of graphs. This generalization forms
the foundation for an extension of the traditional theory of matching.
This theory, whose details will be developed elsewhere,
includes, in addition to further NP-completeness results, new
polynomial algorithms and simple duality results. Some indication of
the nature and scope of this theory are presented here.

If you have any questions or comments regarding this page please send mail to
help@cs.ubc.ca.