[Solved]: What is wrong with this reasoning that finding the genus of a degree 3 bipartite graph is NP-complete?

Problem Detail: 

Finding genus of a biparite graph is $NP$-complete and finding genus of a degree $3$ graph is $NP$-complete and so finding genus of a degree $3$ bipartite graph is $NP$-complete.

Though implication could be right is there any harm in reasoning this way on $NP$-completeness?

Asked By : Turbo

Answered By : Yuval Filmus

You cannot reason in this way. Try proving it formally to see what goes wrong.

Also, consider the following example (which is admittedly slightly different than yours). Chromatic number is NP-complete, even for planar graphs. The 4-coloring problem (i.e., the chromatic number problem with the number of colors fixed at 4) is NP-complete. However, the 4-coloring problem for planar graphs is in P.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/56883

3.2K people like this

 Download Related Notes/Documents