<p>Something has gone wrong, here.  Let us start with the basic definitions.</p>

<p>A <strong>Hamiltonian cycle</strong> 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&lt;n$ and an edge from $v_n$ to $v_1$.</p>

<p>In the <strong>Traveling Salesman Problem</strong> (TSP), we are given $n$ cities and, for <em>every</em> 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.</p>

<p>The <strong>Euclidean Traveling Salesman Problem</strong> 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.</p>

<p>A <strong>Euclidean graph</strong> 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.</p>

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

<p>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.</p>

<p>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: <em>every</em> enumeration of the vertices is a Hamiltonian cycle.</p>

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

<p>Your third claim is that you can find a Hamiltonian cycle in a general graph&nbsp;$G$ by giving every edge weight&nbsp;1 and every non-edge weight&nbsp;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&nbsp;$G$ is not a Euclidean graph so, if your algorithm requires Euclidean graphs, it cannot work on&nbsp;$G$.</p>

CC BY-SA 3.0
2013-10-30T11:23:34.087Z
By the argument of minimum weight circle cannot cross itself, seems is reasonable for a heuristics to consider a graph as a complete graph (in Euclidean space), and then use TSP in the solution of min-HC, this can work for many cases when there are enough connections within neighbors.
Saeed
CC BY-SA 3.0
2013-10-30T11:58:58.933Z
If the asker was claiming just to have a reasonable heuristic for Euclidean TSP, Euclidean MinHam or general Hamiltonian cycle, it would be worth considering such subtleties. But he's actually claiming to have an exact, deterministic, polynomial-time algorithms for all of these problems.
David Richerby
CC BY-SA 3.0
2013-10-30T12:16:10.330Z
I don't know if the asker has a such a big claim, I thought he just found it useful in some few samples and asks whether this is a good heuristic or not, otherwise, yes you are right.
Saeed
CC BY-SA 3.0
2013-10-30T12:30:32.033Z
@Saeed The claim for Euclidean TSP is [here](http://cs.stackexchange.com/questions/14902/traveling-salesman-problem-solution-with-polynomial-algorithm) (Peter Shor showed that the claimed minimal tour there is not minimal; Babibu claims to have fixed the bug and I've not seen him retract the claim).
David Richerby
CC BY-SA 3.0
2013-10-30T12:32:07.050Z
Ok, I didn't know the history and background, thanks.
Saeed
CC BY-SA 3.0
2013-10-30T12:39:31.517Z
@DavidRicherby I don't think you understand what I am saying. Please join me to [chat](http://chat.stackexchange.com/rooms/11285/self-avoiding-walk-in-graph), and then I will edit the question so it will be more clear.
Ilya Gazman
CC BY-SA 3.0
2013-10-30T11:11:38.267Z
2013-10-30T11:11:38.267Z
David Richerby
<p><strong>Short question:</strong> How many self-avoiding-filling-polygons are there in a grid-graph of $n×n$?</p>

<p><strong>Long question:</strong></p>

<p><strong>Edit</strong>: 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.</p>

<p>I am trying to solve <a href="http://en.wikipedia.org/wiki/Hamiltonian_path_problem" rel="nofollow noreferrer">Hamiltonian Circuit Problem (HCP)</a> by converting it to <a href="http://en.wikipedia.org/wiki/Travelling_salesman_problem" rel="nofollow noreferrer">TSP</a>, then finding <strong>non-intersecting paths</strong> (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).</p>

<p>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 <em>non-intersecting paths</em> 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. </p>

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

<p><strong>non-intersecting path:</strong> 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 <a href="http://tsp-vs-world.blogspot.co.il/2013/10/intersections-optimal-tsp-route.html" rel="nofollow noreferrer">geometric proof</a> that TSP solution cannot have any interactions. And I used this code to convert any given path to non-interacting path</p>

<pre><code>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 &lt; newDistance1 + newDistance2
   swap(index1, index2)
   return true
 end if
return false
end function swapIfBetter

function swap(i, j):
  while i &lt; j:
    cities[i], cities[j] = cities[j], cities[i]
    i += 1
    j -= 1
  end loop
end function swap
</code></pre>

<p>*the swap function is taken from my other question <a href="https://cs.stackexchange.com/questions/16418/efficient-way-to-find-intersections">here</a>, created by Yuval Filmus.</p>

<p>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.</p>

CC BY-SA 3.0
2013-10-30T11:15:38.303Z
If your graph has a few number of non-intersecting paths then its almost complete and finding HC is easy by many heuristics.
Saeed
CC BY-SA 3.0
2013-10-30T12:12:32.583Z
@Saeed I am doubt that, it was manually constructed converting Factory to 3-SAT than to Hamiltonian Circuit Problem. Those considered to be hard problems.
Ilya Gazman
CC BY-SA 3.0
2013-10-30T12:30:45.200Z
By Dirac's theorem, if the graph is almost complete, then it has a hamiltonian cycle, there are also some polynomial time algorithm to find such a cycle (by constructive proof of Dirac style theorem e.g see [this](http://www.dharwadker.org/hamilton/hamilton.pdf)). By the way just using heuristics works fine in many cases in such graphs, if you failed to use randomized heuristic for special case then you can use exact algorithm to solve it.
Saeed
CC BY-SA 3.0
2013-10-30T12:47:46.687Z
@Saeed this algorithm require minimum degree, I don't have such restriction, also I can't prove that my algorithm is polynomial-time, and I think that it's probably not, because then I would be able to solve RSA numbers, and I can't do this yet.
Ilya Gazman
CC BY-SA 3.0
2013-10-30T13:07:46.823Z
Ok, I tried to show you a search term, and the main idea behind situations like your case, you can search around it to see whether your case already covered or not and see the ideas, or you can continue in your own way.
Saeed
CC BY-SA 3.0
2013-10-30T13:09:55.990Z
@Saeed I don't understand. You are welcome to join the [chat](http://chat.stackexchange.com/rooms/11285/self-avoiding-walk-in-graph) and explain it to me.
Ilya Gazman
CC BY-SA 3.0
2013-10-30T16:08:49.190Z
The long question makes no sense, and I don't think the short question is research level. The number of self-avoiding Hamiltonian circuits in the $n\times n$ integer grid is $2^{\Omega(n)}$. For example, you can alternate zig-zags of amplitude 1 and 2 and there are at least $2^{n/2}$ choices how to do that.
Sasho Nikolov
CC BY-SA 3.0
2013-10-30T16:11:29.593Z
That said, finding a Hamiltonian cycle in a grid graph without holes is doable in polynomial time, see the Bachelor's thesis of Chris Umans: http://users.cms.caltech.edu/~umans/papers/uthesis.ps
Sasho Nikolov
CC BY-SA 3.0
2013-10-30T16:36:34.030Z
In fact, you have a Hamiltonian cycle in the square grid for each sequence of positive integers $n_1, \ldots, n_k$ such that $n_1 + \ldots + n_k = n$: zig-zag through the first $n_1$ rows, then zigzag through the next $n_2$ rows and so forth. The number of such sequences is $2^{n-1}$.
Sasho Nikolov
CC BY-SA 3.0
2013-10-30T17:35:10.087Z
If you continue to use cstheory for discussing your claims about famous open problems your account will be suspended. As you have been told such discussions are not welcome on cstheory.
Kaveh
<graph-theory><graph-algorithms><shortest-path><hamiltonian-paths>
Self-avoiding walk in Graph
Ilya Gazman
# Self-avoiding walk in Graph

(Asked by: username_0 on 2013-10-30)

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.

**Tags:** graph-theory, graph-algorithms, shortest-path, hamiltonian-paths

> **Comments:**
> **username_1**: If your graph has a few number of non-intersecting paths then its almost complete and finding HC is easy by many heuristics.  
> **username_0**: @username_1 I am doubt that, it was manually constructed converting Factory to 3-SAT than to Hamiltonian Circuit Problem. Those considered to be hard problems.  
> **username_1**: By Dirac's theorem, if the graph is almost complete, then it has a hamiltonian cycle, there are also some polynomial time algorithm to find such a cycle (by constructive proof of Dirac style theorem e.g see [this](http://www.dharwadker.org/hamilton/hamilton.pdf)). By the way just using heuristics works fine in many cases in such graphs, if you failed to use randomized heuristic for special case then you can use exact algorithm to solve it.  
> **username_0**: @username_1 this algorithm require minimum degree, I don't have such restriction, also I can't prove that my algorithm is polynomial-time, and I think that it's probably not, because then I would be able to solve RSA numbers, and I can't do this yet.  
> **username_1**: Ok, I tried to show you a search term, and the main idea behind situations like your case, you can search around it to see whether your case already covered or not and see the ideas, or you can continue in your own way.  
> **username_0**: @username_1 I don't understand. You are welcome to join the [chat](http://chat.stackexchange.com/rooms/11285/self-avoiding-walk-in-graph) and explain it to me.  
> **username_2**: The long question makes no sense, and I don't think the short question is research level. The number of self-avoiding Hamiltonian circuits in the $n\times n$ integer grid is $2^{\Omega(n)}$. For example, you can alternate zig-zags of amplitude 1 and 2 and there are at least $2^{n/2}$ choices how to do that.  
> **username_2**: That said, finding a Hamiltonian cycle in a grid graph without holes is doable in polynomial time, see the Bachelor's thesis of Chris Umans: http://users.cms.caltech.edu/~umans/papers/uthesis.ps  
> **username_2**: In fact, you have a Hamiltonian cycle in the square grid for each sequence of positive integers $n_1, \ldots, n_k$ such that $n_1 + \ldots + n_k = n$: zig-zag through the first $n_1$ rows, then zigzag through the next $n_2$ rows and so forth. The number of such sequences is $2^{n-1}$.  
> **username_3**: If you continue to use cstheory for discussing your claims about famous open problems your account will be suspended. As you have been told such discussions are not welcome on cstheory.  

---

## 1 answers

### Answer by username_4 on 2013-10-30. Score: 3

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

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$.

> **Comments:**
> **username_1**: By the argument of minimum weight circle cannot cross itself, seems is reasonable for a heuristics to consider a graph as a complete graph (in Euclidean space), and then use TSP in the solution of min-HC, this can work for many cases when there are enough connections within neighbors.  
> **username_4**: If the asker was claiming just to have a reasonable heuristic for Euclidean TSP, Euclidean MinHam or general Hamiltonian cycle, it would be worth considering such subtleties. But he's actually claiming to have an exact, deterministic, polynomial-time algorithms for all of these problems.  
> **username_1**: I don't know if the asker has a such a big claim, I thought he just found it useful in some few samples and asks whether this is a good heuristic or not, otherwise, yes you are right.  
> **username_4**: @username_1 The claim for Euclidean TSP is [here](http://cs.stackexchange.com/questions/14902/traveling-salesman-problem-solution-with-polynomial-algorithm) (Peter Shor showed that the claimed minimal tour there is not minimal; Babibu claims to have fixed the bug and I've not seen him retract the claim).  
> **username_1**: Ok, I didn't know the history and background, thanks.  
> **username_0**: @DavidRicherby I don't think you understand what I am saying. Please join me to [chat](http://chat.stackexchange.com/rooms/11285/self-avoiding-walk-in-graph), and then I will edit the question so it will be more clear.  

---

