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$.

  • $\begingroup$ See also here. $\endgroup$ – Raphael Apr 21 '13 at 14:44

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.