Partition into Isomorphic Subgraphs

Input

Graphs $G = (V, E)$ and $H = (V', E')$ with $|V| = q |V'|$ for some $q \in \mathbb{Z}^{+}$.

Question

Can the verticies of $G$ be partitioned into $q$ disjoint sets $V_1, V_2, \dots, V_q$ such that, for $1 \leq i \leq q$, the subgraph of $G$ induced from $V_i$ is isomorphic to $H$?

Classes

• NP-complete

Comments

Remains NP-complete for any fixed $H$ that contains at least 3 vertices. The analogous problem in which the subgraph induced by $V_i$ needs only to have the same number of vertices as $H$ and contains a subgraph isomorphic to $H$ is also NP-complete, for any fixed $H$ that contains a connected component of three or more vertices. Both problems can be solved in polynomial time (by matching) for any $H$ not meeting the stated restrictions.

Proofs

NP-complete

Transformation from 3-Dimensional Matching (Kirkpatrick & Hell, 1978).

Reducible from

• 3-Dimensional Matching

References

• Kirkpatrick, D. G., & Hell, P. (1978). On the completeness of a generalized matching problem. Proceedings of the Tenth Annual ACM Symposium on Theory of Computing - STOC ’78. https://doi.org/10.1145/800133.804353