# Non-deterministic algorithm for solving figure of 8

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

Consider the following problem, called the ﬁgure-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

-
Hint: If I gave you a sequence $(v_0,v_1, \ldots, v_{k-1})$ could you check if it was a valid yes instance in polynomial time? – Marc Khoury Jan 4 '13 at 13:17

@sazap10: That's where the non-determinism comes in, as Pål GD said, the algorithm can "guess" a $k$ and a sequence of that length, then it checks deterministically that it's correct. If a correct answer exists, the non-determinism guarantees that the algorithm will guess correctly. If no answer exists, it will guess wrong, which is why the answer needs to be checked. – Luke Mathieson Jan 8 '13 at 1:00