The $H$-matching problem asks to partition the vertices of an input graph $G$
into sets of size $k=|V(H)|$, each of which induces a subgraph of $G$
isomorphic to $H$. The $H$-matching problem has been classified as polynomial
or NP-complete depending on whether $k\leq 2$ or not. We consider a variant
of the problem, in which a homomorphism from $G$ to $H$ is given, so that
$G$ is $k$-partite, and each chosen set of size $k$ must contain exactly
one vertex from each of the $k$ parts. We classify the problem as polynomial
or NP-complete depending on whether $H$ is a forest or not.

The polynomial case with $H$ a forest generalizes to the case where each set of
size $k$ must contain a subgraph satisfying certain degree constraints,
provided that the skip between consecutive allowed degrees is at most two;
a skip of at least three gives NP-completeness. More generally, one may
specify which sets of incident edges for a vertex in the subgraph are allowed,
and the problem has complexity related to delta-matroids. Several of the
polynomial cases extend to a weighted version.

An optimization variant of the problem asks to maximize the number of chosen
sets of size $k$ that induce a subgraph isomorphic to $H$. This problem is
shown polynomial if every component of $H$ is a path, and NP-complete
otherwise. The polynomial cases extend to a weighted version, while the
NP-complete cases are hard to approximate within a constant even for bounded
degree instances, allowing a $\frac{k}{2}+\epsilon$ approximation. We similarly
classify the problem of asking that each chosen set of size $k$
contain at least $r$ edges forming a connected subgraph, for all $H$
and $r$, and nearly classify the case where the $r$ edges are not required
to form a connected subgraph.