# Complexity of Hamiltonian path and clique problem

I came across this question. If we want to check if a graph contains both Hamiltonian path and clique. Would this problem be NPC.

I knew that clique contains a Hamiltonian path and both problems are NPC, but I am uncertain if something would be different if we check it in same time.

• Why would it be different? Do you mean more difficult? – Chill2Macht May 1 '16 at 21:17

In the clique problem we are required to determine if there exists a clique of a certain size (given as input), so the observation that every clique contains a Hamiltonian path won't help much (a graph $G$ with $n$ vertices may contain cliques of size $<n$, but not have a Hamiltonian path).
$Clique=\left\{\langle G,k\rangle | \hspace{1mm} G \text{ contains a clique of size }\ge k\right\}$
$HPath=\left\{G | \hspace{1mm} G \text{ contains a Hamiltonian path}\right\}$
$L=\left\{\langle G,k\rangle | \hspace{1mm} G \text{ contains a clique of size }\ge k \land G \text{ contains a Hamiltonian path}\right\}$.
$L$ can be shown to be NP-complete using a simple reduction from $HPath$ (think about how to change the instance to the HPath problem, to an instance of $L$, without ruining the properties of the graph).