I am trying to show a different form of Hamiltonian cycle problem is NP Hard. The problem is as follows.

We have a directed graph and each node can have at most 3 outgoing edges. Determine if this graph has a Hamiltonian cycle.

Is this problem NP hard?

I just need to find a problem to reduce to my problem but could achieve to find none.

3SAT looks friendly to me as it has 3-termed clauses but no more I progressed.

  • 2
    $\begingroup$ Try reduction from the usual Hamiltonian cycle problem. $\endgroup$ – Yuval Filmus Mar 28 '19 at 13:26
  • $\begingroup$ @YuvalFilmus yeah but I do not want answer but just a hint to go on $\endgroup$ – Davis Mar 28 '19 at 14:59
  • 1
    $\begingroup$ I already gave you a hint. Try a reduction from Hamiltonian cycle. I don't know if the hint works, but it seems like a good thing to try. $\endgroup$ – Yuval Filmus Mar 28 '19 at 15:01
  • 3
    $\begingroup$ Hint: When reducing from Hamiltonian Cycle as suggested by @YuvalFilmus, you can add many more "helping" vertices to each original vertex, provided you can figure out a way to let them all be visited when the original vertex is. $\endgroup$ – j_random_hacker Mar 28 '19 at 15:02
  • 1
    $\begingroup$ If you has figured out this problem, please write an answer (yes, you can answer your own question). $\endgroup$ – xskxzr Mar 29 '19 at 17:37

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.