I need to prove that the following problem is NP-complete: We have $n$ diplomats from $n$ countries and we need to seat them around a round table. We also get a list of diplomats who don't get along with each other, and we can't seat them next to each other.

I thought about a reduction from the $n$-color graph problem (graph coloring) which is NP-complete, but I'm not sure what the reduction is exactly. Can somebody help with that?

  • 4
    $\begingroup$ I think you'd have an immediate reduction from the Hamiltonian Cycle problem. $n$-coloring with $n$ diplomats seems not really suitable. $\endgroup$ – ttnick Jul 31 '18 at 12:14
  • 1
    $\begingroup$ @PHPNick I meant k-color where every two diplomats that don't get along with each other are in the same color and we will find a way that every two nodes in every edge have different colors (I'm not sure if it's suitable, but that what I meant). Do you have an idea for a reduction from Hamiltonian cycle? $\endgroup$ – Barry Jul 31 '18 at 12:54
  • 2
    $\begingroup$ Your problem is the Hamiltonian cycle problem in (rather thin) disguise. I encourage you to work this out. $\endgroup$ – Yuval Filmus Jul 31 '18 at 13:41
  • $\begingroup$ Perhaps you can answer your own question? $\endgroup$ – Yuval Filmus Aug 5 '18 at 20:18

Your Answer

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

Browse other questions tagged or ask your own question.