NP hardness through Restriction

Question

Let's say I have a decision problem $P$ on graphs for which I know that it is NP-hard on graphs with maximum degree $d$. Does this then imply that it is NP-hard on $d$-regular graphs? Although it might seem obviously true, maybe it is inherent in the reduction to show that $P$ is hard, that some vertices have degree less than $d$.

Answer 1

No, it is not true in general.

A general problem being NP-Hard does not imply a specialization will be NP-Hard. It is true the other way round.

For instance, MAX-CUT is NP-Hard for general graphs, but for the class of planar graphs, it is in P.

In your case, the $d$-regular graphs are a special case of graphs of max degree $d$, so NP-Hardness for max degree $d$ is not an automatic proof of NP-Hardness of $d$ regular graphs.

In fact, for a concrete example, look at this cstheory question: Is there a problem that is easy for cubic graph but hard for graphs with maximum degree 3? with the following answer(by David Eppstein) in the affirmative (copied for convenience):

Here's a reasonably natural one: on an input $(G,k)$, determine whether $G$ has a connected regular subgraph with at least $k$ edges. For 3-regular graphs this is trivial, but if max degree is 3 and the input is connected, not a tree, and not regular, then the largest such subgraph is the longest cycle, so the problem is NP-complete.