Answer Happy

A Hamiltonian path on a directed graph G = (V, E) is a path that
visits each vertex in V
exactly once. Consider the following variants on Hamiltonian
path:
(a) Give a polynomial-time algorithm to determine whether a
directed graph G
contains either a cycle or a Hamiltonian path (or both). Given a
directed graph G,
your algorithm should return true when a cycle or a Hamiltonian
path or both and
returns false otherwise.

(b) Show that it is NP-hard to decide whether a directed graph G’
contains both a
cycle and a Hamiltonian Path, by giving a reduction from the
HAMILTONIAN
PATH problem: given a graph G, decide whether it has a Hamiltonian
path.
(Recall that the HAMILTONIAN PATH problem is
NP-complete.)