World's most popular travel blog for travel bloggers.

# [Solved]: Complexity of Hamiltonian path and clique problem

, ,
Problem Detail:

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.

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\}$

Since the instances to the problems are not of the same type, it isn't really interesting to talk about their intersection (which is empty), so what you probably have in mind is the set:

$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).