# 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 at 13:17

## 1 Answer

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.

-
I thought that the input to the algorithm was the Graph itself not just the sequence of vertices. If it is just verifying the sequence then i dont really need a non-deterministic algorithm for that – sazap10 Jan 7 at 12:00
Yes, the input is indeed the graph itself, but the non-determinism allows you to "guess the correct answer" as long as it exists. Then all that's left is to verify that the answer is indeed correct. – Pål GD Jan 7 at 12:09
But shouldnt the algorithm also be generating these sequences? eg "pick a node, add to sequence, pick an adjacent node, add to sequence,.."? – sazap10 Jan 7 at 12:59
@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 at 1:00