1
$\begingroup$

Given a graph $G=(V,E)$, all the vertices $v \epsilon V$ are labeled with values from $\{1,2,...\ldots n\}$ where $|V| = n$ such that for all edges $(x,y) \epsilon E$ such that $|label(x) - label(y)| \ge 2$. We have to determine whether such a labeling is possible for a graph.

Now I have to prove that doing so is a NP-complete problem. While showing that it belongs to NP is straightforward, I am unable to think of which NP-complete problem to be considered for reduction in polynomial time to this problem as part of the proof?

$\endgroup$
1
$\begingroup$

Given a graph $G$, consider its complement $G'$. The graph $G'$ is a yes instance of your problem if its vertices can be ordered so that adjacent vertices are not connected by an edge in $G'$. In other words, $G'$ is a yes instance of your problem if the vertices of $G$ can be ordered so that adjacent vertices are connected. So $G'$ is a yes instance of your problem if and only if $G$ has a Hamiltonian path.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.