How does this non-deterministic algorithm to find if a Hamiltonian path exists work?

Question

I have read of an algorithm that a non-deterministic Turing machine $N$ can run to determine whether a given graph $G$ has a Hamiltonian path from the start node $s$ to a certain node $n$:

1. Write a list of $x$ numbers $p_1, p_2, p_3 ... p_x$, where $x$ is the number of nodes in $G$. Each number in this list is non-deterministically selected to be from 1 to $x$.

2. Check for repetitions in this list. If a repetition exists, reject.

3. Check whether both $s = p_1$ and $n = p_x$. If either do not hold, reject.

4. For each $i \in [1, x - 1]$, check whether $(p_i, p_{i + 1})$ is an edge of $G$. If any are not, reject.

5. Accept.

I do not understand how this algorithm works. Specifically, in step 1, why am I making a list of random (potentially repeating) numbers from 1 to $x$ (What does this list have to do with the nodes of $G$?)?

Likewise, in step 4, why does $(p_i, p_{i + 1})$ represent a potential edge in $G$?

Answer 1

There's a couple of bits of information that are key to making this make sense:

1. Each $p_{i}$ should be a label for a vertex in $G$. Typically $p_{i} \in [1,x]$, but it's not compulsory that you have to label the vertices from 1 to $x$. So the first step is effectively producing a putative list of vertices that could be a path. The rest just checks that it is actually a path (a hence why $(p_{i},p_{i+1})$ could be an edge).

2. The list is not random. It is selected non-deterministically. This is most definitely not the same as randomly selected. Non-determinism is a special theoretical property where a non-deterministic machine can "guess" a correct answer if it exists, however correct also has a special meaning, in that it selects an answer that will lead to an accepting state if such an answer exists. This may not be the right answer, just one that will make the Turing Machine say Yes - so we still have to check it.

So the algorithm guesses really cleverly a list (in fact an ordering) of all the vertices of the graph, and then checks that it actually makes a Hamiltonian Path from $s$ to $n$.