# Covering a complete graph with n copies of an arbitrary graph: NP-complete?

Given a complete graph $G$, an arbitrary graph $H$, and a positive integer $n$, are there subgraphs $A_1,\dots,A_n$ of $G$ (not necessarily disjoint) such that their union is $G$, and each of them are isomorphic to $H$?

This is a problem which I believe is NP-complete, but I am unsure if it is actually so. Any ideas of how to prove this?

Notes:

• If $G$ is instead allowed to be an arbitrary graph, then this is clearly at least as hard as subgraph isomorphism, which is NP-complete.
• If $G$ is allowed to be an arbitrary graph, and $A_1,\dots,A_n$ are required to be isomorphic to a subgraph of $H$, instead of the entire graph $H$, then the problem can be reduced from vertex cover (which is NP-complete) by setting $H$ to be a star graph with the number of spokes equal to the number of nodes in $G$.
• The problem where $H$ must also be a complete graph is called "covering design", and has some discussion here, with closed forms for when $H$ has 3 or 4 nodes. Finding algorithm for this is apparently an open problem.
• If $G=K_m$, is $m$ given in binary or unary? – Willard Zhan Mar 12 '18 at 17:19
• @WillardZhan I didn't think about it before. (I mainly thought about cases where $H$ is nearly as large as $G$.) Let's say I'm interested in answers of either variant. – Theemathas Chirananthavat Mar 12 '18 at 20:28
• Another special case that looks hard (an open problem since 1967) is when $H$ is a collection of vertex-disjoint cycles: en.wikipedia.org/wiki/Oberwolfach_problem – j_random_hacker Mar 13 '18 at 14:51
• Do you mean a subgraph by a subgraph induced by a subset of vertices of $G$ (which is the definition used in subgraph isomorphism problem)? How do you define the union of two subgraphs? – xskxzr Oct 27 '18 at 19:12