1
$\begingroup$

Let G be a graph

Suppose G has N vertices

Let H be the set of Hamiltonian paths in G

If G has a Hamiltonian path, then by systemically changing our start vertex and then nondeterministically walking the remaining N vertices, we will find it (i.e. take a "random walk").

Can we nondeterministically walk such that if there's a Hamiltonian path, we'll choose the least next vertex? Let's call this the least Hamiltonian path.

For example, let G1 be a graph with 3 vertices and all possible edges

Then there are 6 elements of H: 123, 132, 213, 231, 312, 321

In G1, if our start vertex is 3, then there are 2 Hamiltonian paths: 312 and 321.

By nondeterministically choosing the least next vertex of the Hamiltonian if one exists, then we'll always choose the same Hamiltonian path: 312 in this case (because our start is 3 and 1 < 2).

If we are allowed to nondeterministically choose the least next vertex, then we can nondeterministically traverse the same Hamiltonian path multiple times.

We ensure the least Hamiltonian path has no duplicate vertices. Pseudocode:

function hasDuplicates(leastHPath):
  for (j in N):
    for (k in N):
      if (k == j) continue;
      if (leastHPath[j] == leastHPath[k]:
        return false;
  return true;

Does this algorithm (nondeterministically choosing the least Hamiltonian path if one exists, ensuring the count of vertices = N and ensuring there are no duplicates) decide Hamiltonian paths? If so, what is its space complexity?

$\endgroup$
1
  • $\begingroup$ What does "nondeterministically choose the least next vertex" mean? What is a "least" vertex? What is a least "next vertex"? Why would that be nondeterministic? $\endgroup$ – D.W. Apr 16 at 19:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.