4
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ Try reduction from the usual Hamiltonian cycle problem. $\endgroup$
    – Yuval Filmus
    Commented Mar 28, 2019 at 13:26
  • $\begingroup$ @YuvalFilmus yeah but I do not want answer but just a hint to go on $\endgroup$
    – Davis
    Commented Mar 28, 2019 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
    Commented Mar 28, 2019 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
    Commented Mar 28, 2019 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
    Commented Mar 29, 2019 at 17:37

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.