Abstract:
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.