World's most popular travel blog for travel bloggers.

[Solved]: Complexity of Hamiltonian path and clique problem

, , No Comments
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.

Asked By : Someguy

Answered By : Ariel

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

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback