-5
$\begingroup$

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.

$\endgroup$

closed as off-topic by Kaveh Oct 30 '13 at 17:36

This question appears to be off-topic. The users who voted to close gave this specific reason:

If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ If your graph has a few number of non-intersecting paths then its almost complete and finding HC is easy by many heuristics. $\endgroup$ – Saeed Oct 30 '13 at 11:15
  • 2
    $\begingroup$ 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). 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. $\endgroup$ – Saeed Oct 30 '13 at 12:30
  • 2
    $\begingroup$ 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. $\endgroup$ – Sasho Nikolov Oct 30 '13 at 16:08
  • 2
    $\begingroup$ 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}$. $\endgroup$ – Sasho Nikolov Oct 30 '13 at 16:36
  • 5
    $\begingroup$ 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. $\endgroup$ – Kaveh Oct 30 '13 at 17:35
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Saeed Oct 30 '13 at 11:23
  • $\begingroup$ 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. $\endgroup$ – David Richerby Oct 30 '13 at 11:58
  • $\begingroup$ 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. $\endgroup$ – Saeed Oct 30 '13 at 12:16
  • 2
    $\begingroup$ @Saeed The claim for Euclidean TSP is here (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). $\endgroup$ – David Richerby Oct 30 '13 at 12:30
  • $\begingroup$ Ok, I didn't know the history and background, thanks. $\endgroup$ – Saeed Oct 30 '13 at 12:32

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