Is the dominating set problem restricted to planar bipartite graphs of maximum degree 3 NP-complete?

Does solving a restricted version of an NP-complete problem in polynomial-time imply that all NP-complete problems, when restricted to that version, can be solved in polynomial-time?

• For example, restricted version in the sense that a planar graph be considered instead of a general graph.

• Answer:

  No. Because the polynomial time transformation (the reduction) might not preserve the structure, for example planarity, while it computes and outputs the new graph. NP-completeness does not care much about the instances except their equivalence. Suppose there is an NP-complete  problem P, which you can solve on graph class X in polynomial time. Now you want to use this algorithm to solve any problem Q, which is in NP, on graph class X in polynomial time. Of course, since P is NP-complete, there exists a polynomial time reduction from Q to P. So you get a graph, which belongs to graph class X, and use the reduction. But the reduction might take you out of the graph class X, where P is not known to be polynomial time solvable. That's where the obvious approach fails. As a consequence of a negative answer to your question, restricted graph classes become interesting. For example, most NP-complete problems are easy on tress, but there are some which remain NP-complete even on trees (like finding the achromatic number). Same it true for Bipartite graphs, Perfect graphs, Planar graphs etc. This tells us that problems behave differently on different graph classes, and that we have to look deeper if we want to know the relationship better.