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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.