Packings by Complete Bipartite Graphs
Pavol Hell, David G. Kirkpatrick · SIAM Journal on Algebraic and Discrete Methods · 1986
Given any set $\mathcal{B}$ of complete bipartite graphs, we ask whether a graph H admits a $\mathcal{B}$-factor, i.e., a spanning subgraph, each of whose components is a member of $\mathcal{B}$. More generally, we seek in H a maximum $\mathcal{B}$-packing, i.e., a $\mathcal{B}$-factor of a maximum size subgraph of H. We first treat the interesting special case when $\mathcal{B}$ is a set of stars. The results are generalized to arbitrary $\mathcal{B}$ in the last section. We prove for most of these problems that they are $\mathcal{N}\mathcal{P}$-hard; we also show that the remaining problems admit polynomial algorithms based on augmenting configurations. The simplicity of these algorithms, as well as the implied min-max theorems, resemble the theory of matchings in bipartite, rather than general, graphs.