Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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

share|improve this question
2  
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
add comment

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
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 '13 at 12:00
1  
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 '13 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 '13 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 '13 at 1:00
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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