Can a natural graph problem be universally hard?

Question

Is there a natural $\mathsf{NP}$-complete graph problem, which remains $\mathsf{NP}$-complete even when it is restricted to any polynomial-time recognizable graph class? To avoid degenerated cases, let us consider only dense graph classes, in which the number of non-isomorphic $\leq n$-vertex graphs grows exponentially with $n$.

Notes:

(1) Both a "yes" or a "no" answer would be quite interesting. If the answer is yes, then we would have a natural $\mathsf{NP}$-complete graph property that could be called universally hard, because it preserves hardness even when restricted to any reasonable graph class. If the answer is no, it would mean that every natural $\mathsf{NP}$-complete graph property can be made easy on some nontrivial graph class.

(2) It is important to consider only polynomial-time recognizable graph classes, to exclude that the hardness of the property is simply shifted to the class. For example, 3-COLORABILITY becomes trivial when restricted to 3-colorable graphs.

Answer 1

The definition of "natural" is a bit fuzzy, but there's a trivial reason the answer here is likely "no". Suppose to the contrary that there is such a problem, $P$. If $P$ only acts on the first component of the provided graph, then $P$ is easy on the class of graphs where the first component is an instance of $P$ and the second component encodes a certificate of $P$ holding on the first component. Further, this class of graphs is polytime recognizable. Indeed, the same holds true if we can designate a portion of the graph as a "this is a certificate and not part of the problem component", in the sense that we can sneak this certificate in without affecting the true answer.

Most "natural" problems, as far as I can tell, allow for the designation of such a piece of the graph. Here are a few examples

• Max Clique: just ensure that the certificate portion of the graph does not have a large clique (eg. encode it using a matching)
• Hamiltonian Path: the tail node is replaced by a certificate graph which has an easy-to-find Hamiltonian path of its own
• Hamiltonian Circuit: same as Hamiltonian path except some designated vertex is replaced with a certificate graph containing a Hamiltonian cycle
• Max Cut: this doesn't affect the solution as long as there are no edges to the rest of the graph, so we just ensure that the max cut here is easy to find (eg. we encode using a matching)
• Vertex cover: the certificate is again encoded by a matching

We ensure that the certificate portion of the graph is designated as such, so to not lose it in the rest of the graph (though designating them implicitly via the graph structure is probably easy enough for most "natural" problems).

Since NP-complete problems cannot be sparse unless $P=NP$ (Mahaney's theorem), neither can this construction, satisfying your non-triviality constraint.