Non-deterministic algorithm for solving figure of 8

Question

I am struggling in trying to figure out a non-deterministic algorithm for the following problem.

Consider the following problem, called the figure-of-eight problem (FOE). An instance is an undirected graph $G = (V,E)$ with vertices $V$ and edges $E$. $G$ is a yes-instance if there is a sequence of vertices $(v_{0},v_{1},...,v_{k+1})\ (some\ k \geq 6)$ such that

• Each pair $(v_{i},v_{i+1})$ is an edge $(each\ i < k − 1)$ and $(v_{k−1},v_{0})$ is an edge.

• Every vertex in $V$ occurs at least once in the sequence.

• There is $j$ with $2 < j < k − 2$ such that $v_{0} = v_{j}$.

• No other vertex in the sequence is counted twice, i.e. if $v_{s} = v_{t} (any\ s,t < k)$ then either $s = t$ or ${s,t} = {0,j}$.

If there is no such sequence of vertices then $G$ is a no-instance of FOE.

Thanks

Answer 1

If you want to prove that this problem is in NP, then all you have to do is to come up with a polytime algorithm that verifies the correctness of a solution. I.e., in polynomial time, verify that a given sequence satisfies the conditions you wrote.

This should also help you in actually construct the non-deterministic algorithm.