Self-avoiding walk in Graph [closed]

Question

Short question: How many self-avoiding-filling-polygons are there in a grid-graph of $n×n$?

Long question:

Edit: This question is not about p = np. I am searching for a way to calculate the numbers of Self-avoiding circuit paths in TSP. It's not a typical Self-avoiding circuit but it have my own definition, I call it: non-intersecting path, and it's defined by my pseudo code that is use both for Euclidean and not Euclidean graphs.

I am trying to solve Hamiltonian Circuit Problem (HCP) by converting it to TSP, then finding non-intersecting paths (see my definition on the bottom of the page). Then keeping the path with the shortest weight, randomly ruined it by swapping random vertices along the path(I am storing the path in array and randomly swapping indexes), then fix it by converting it to non-interacting path again, and doing this again until I solve the HCP(I gave the wight 1 to all the edges that I got and weight 2 for all the rest when converting to TSP, so when I find a route where all the weights are 1 I know that I found the solution).

Using this method I been able to solve HCP passels with 300 vertexes and around 800 edges. I suspect that the reason that I been able to do that, is that the number of non-intersecting paths is very small. So I did a test, I created a brute force program and test it on inputs of 20 cities, I found that there wasn't any input(from my random generations) with more than 300 non-intersecting paths. This "evidence" makes me very optimistic about my suspicious that the number of non-intersecting paths in compare to number of vertices is not big, how ever a proof is required.

So please help me to find a proof for whether my suspicious is true or not.

non-intersecting path: In Euclidean graph where each vertex is a point on the 2D plane, so the weight of each edge is the Euclidean distance between the vertices. I found a geometric proof that TSP solution cannot have any interactions. And I used this code to convert any given path to non-interacting path

Read input into cities array
do
  iterate over cities from i = 0
    iterate over cities from j = i
      if swapIfBetter(i, j) then set swapFound to true
while not swapFound

function swapIfBetter(index1, index2)
  if index1 equals 0 and index2 equals cities size - 1
    return false

 initialize cities a,b,c,d
 set a to cities at index index1
 set b to cities at index (index1 - 1) unless index1 equals 0 in that case set it to (cities size - 1)
 set c to cities at index index2
 set d to cities at index (index2 + 1) unless index2 equals (cities size - 1) in that case set it to 0

 initialize currentDistance1 to distance between a and b
 initialize currentDistance2 to distance between c and d

 initialize newDistance1 to distance between b and c
 initialize newDistance2 to distance between a and d

 if currentDistance1  + currentDistance2 < newDistance1 + newDistance2
   swap(index1, index2)
   return true
 end if
return false
end function swapIfBetter

function swap(i, j):
  while i < j:
    cities[i], cities[j] = cities[j], cities[i]
    i += 1
    j -= 1
  end loop
end function swap

*the swap function is taken from my other question here, created by Yuval Filmus.

The most interesting thing is when I used this code on not Euclidean graph it also worked. So I define non-interacting path, by path that been converted this way.

Answer 1

Something has gone wrong, here. Let us start with the basic definitions.

A Hamiltonian cycle is a cycle is an enumeration $v_1, \dots, v_n$ of the vertices of a graph such that there is an edge from $v_i$ to $v_{i+1}$ for $1\leq i<n$ and an edge from $v_n$ to $v_1$.

In the Traveling Salesman Problem (TSP), we are given $n$ cities and, for every pair of cities, the non-negative cost of traveling between them. We want to know the minimum cost of starting at the city of our choice, visiting every other city exactly once, in the order of our choice, and returning directly to the start point. There are no restrictions on the costs: it could cost \$1 to get from London to Paris, \$1 to get from Paris to New York but \$1,000,000 to get directly from London to New York. Thus, TSP is the problem of finding a minimum-weight Hamiltonian cycle in a complete graph with arbitrary non-negative weights.

The Euclidean Traveling Salesman Problem is TSP with the restriction that the cities are distinct points in Euclidean space and the cost of getting from A to B is the distance between those two points. Euclidean TSP is the problem of finding a minimum-weight Hamiltonian cycle in an arbitrary Euclidean complete graph.

A Euclidean graph is an embedding of a graph in the Euclidean plane. Each vertex is a point and each edge is a straight line between its endpoints. If there is an edge between $x$ and $y$, the weight of that edge is its length.

Yet a third problem is to find the minimum weight Hamiltonian cycle in a Euclidean graph, which I'll call Euclidean MinHam.

You appear to be confusing Euclidean TSP and Euclidean MinHam. In Euclidean TSP, there is an edge between every pair of vertices; in Euclidean MinHam, there may or may not be an edge between every pair of vertices. This is crucially important.

Your claimed algorithm for Euclidean TSP is to generate a Hamiltonian cycle and then adjust it until you get one of minimum weight. I do not believe that will give an efficient algorithm but it is possible that it will. A key point is that generating a Hamiltonian cycle is trivial because the graph you start with is a complete graph: every enumeration of the vertices is a Hamiltonian cycle.

Your second claim is that you can solve Euclidean MinHam by the same method. However, to even get this started, you need to find some Hamiltonian cycle in your Euclidean graph, to begin the optimization process. This problem is already NP-hard.

Your third claim is that you can find a Hamiltonian cycle in a general graph $G$ by giving every edge weight 1 and every non-edge weight 2, and then feeding the resulting graph to your Euclidean TSP algorithm. This cannot possibly work. Your Euclidean TSP algorithm is supposed to work by exploiting the geometric properties of the problem (for example, that the minimum-weight solution cannot cross itself). This property does not hold for general weighted graphs. Your transformed version of $G$ is not a Euclidean graph so, if your algorithm requires Euclidean graphs, it cannot work on $G$.