1
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ is it because every planar graph has a $4$ coloring? $\endgroup$ – T.... May 2 '16 at 10:29
  • $\begingroup$ Yes, that's the idea. $\endgroup$ – Yuval Filmus May 2 '16 at 11:21
5
$\begingroup$

What is wrong with the reasoning is that you are placing additional restrictions and thus simplifying the class of problems. Even if each of the conditions alone grants $NP$-completeness, their intersection may make the result simpler.

What would work as a minimal example of the fault in the reasoning for me:

1) It takes an infinite time to list all primes.

2) It takes an infinite time to list all even numbers.

3) It does not take an infinite time to list all even primes.

$\endgroup$
  • $\begingroup$ That is good posting. $\endgroup$ – T.... May 2 '16 at 10:39
5
$\begingroup$

Intuitively, graphs with property $X$ and graphs with property $Y$ can be very different from graphs with both properties $X$ and $Y$.

For example, consider the following (this is very much along the lines of Yuval's answer). Deciding if there is a dominating set on at most $k$ vertices is NP-complete for bipartite graphs. The same is true for claw-free graphs. But this is certainly not true for bipartite claw-free graphs, as each such graph is a collection of disjoint cycles and paths.

$\endgroup$

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.