On the complexity of overlaying a hypergraph with a graph with bounded maximum degree

Let G and H be respectively a graph and a hypergraph defined on a same set of vertices, and let F be a graph. We say that G F-overlays a hyperedge S of H if the subgraph of G induced by S contains F as a spanning subgraph, and that G F-overlays H if it F-overlays every hyperedge of H. For a fixed graph F and a fixed integer k, the problem (∆ ≤ k)-F-Overlay consists in deciding whether there exists a graph with maximum degree at most k that F-overlays a given hypergraph H. In this paper, we prove that for any graph F which is neither complete nor anticomplete, there exists an integer np(F) such that (∆ ≤ k)-F-Overlay is NP-complete for all k ≥ np(F).