0
$\begingroup$

I have an Euclidean graph: 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 every optimal TSP solution contains no intersections.

How many non-intersecting routes could be there? Or in other words: what is the probability to guess an optimal solution to a TSP problem if we just enumerate or sample non-intersecting routes?

Edit: I want to ignore the case that D.W. mentioned. For every path that you can swap between two neighbors vertices(If we represent the path as an array of vertices so neighbors will be two vertices with consecutive indexes) without changing its non-intersecting quality, all of those paths will be considered as one.

Edit I found that this kind of removing crossings from the graph also know as 2-OPT

Improve this question
$\endgroup$
10
  • $\begingroup$ If you found an algorithm that provably does that, then you solved the problem of finding a Hamiltonian path in a grid graph, which is $\mathcal{NP}$-complete. I doubt this is true. $\endgroup$ – G. Bach Oct 26 '13 at 14:54
  • $\begingroup$ @G.Bach I been testing on random and test data with thousands of cities, and I succeed finding non intersecting route in them all, more than that, I can prove that it is $O(N^2)$. How ever this is not related to the question. If you like we can discuss about that in chat. $\endgroup$ – Ilya Gazman Oct 26 '13 at 15:13
  • $\begingroup$ see also shortest nonintersecting path for graph embedded in euclidean plane $\endgroup$ – vzn Oct 26 '13 at 16:03
  • 4
    $\begingroup$ I'm not really interested in discussing something you didn't even give an attempt at a proof for. Experimental results are irrelevant in formal contexts, and I'm not overstating this. If you want to prove something in math (and graph theory is math), then you have to do it using mathematical methods. $\endgroup$ – G. Bach Oct 26 '13 at 17:36
  • 1
    $\begingroup$ To see that there are exponential many non crossing routes, just pick an $n \times n$ grid graph (two nodes are connected if and only if they are adjacent horizontally or vertically) and see how easily you can find an exponential number of hamiltonian paths. $\endgroup$ – Vor Nov 3 '13 at 16:47
10
$\begingroup$

There are exponentially many such routes.

Think of a sequence of $n$ diamonds. At each diamond, you can go either left or right, independently of what you do at all other diamonds. This leads to $2^n$ paths, each of which is non-intersecting. Now the complete graph on those vertices contains all of these paths, plus some more, so this is a lower-bound on the number of non-intersecting paths.

Therefore, you can't hope to find the optimal one in polynomial time by guessing or enumerating non-intersecting routes.

You probably could have guessed or suspected this, from the fact that Euclidean TSP is NP-complete....

Improve this answer
$\endgroup$
5
  • $\begingroup$ I disagree with you, diamonds are not legal route in TSP, as they have 3 edges connected to one vertex. Also if you cut the extra edge, you can't connect two diamonds as, again, you will gave more than 2 edges connected to the same vertex. $\endgroup$ – Ilya Gazman Oct 26 '13 at 15:55
  • 4
    $\begingroup$ @Babibu, please try to read more carefully. I didn't say the diamond was the route. I said consider a graph of diamonds; that graph has exponentially many routes. The number of routes in any graph that contains such diamonds (such as a complete Euclidean graph) is at least as large, i.e., also exponentially large. $\endgroup$ – D.W.♦ Oct 26 '13 at 18:51
  • $\begingroup$ @D.W. The problem is he is asking for Hamiltonian cycles that have no crossing edges, so what you'd have to show is that there are graphs where there are exponentially many of those. Just any non-crossing paths won't do. $\endgroup$ – G. Bach Oct 26 '13 at 19:13
  • 3
    $\begingroup$ It's easy to modify this example to give exponentially many Hamiltonian paths or cycles. For paths, think of a sequence of points $(0,0), (1, 0), (1, 1), (2, 0), (3, 0), (3,1), \ldots, (2k, 0), (2k+1, 0), (2k+1, 1)$. You can go either from $(0, 0)$ to $(1, 0)$ and then $(1, 1)$ and $(2, 0)$, or to $(1,1)$, $(1, 0)$ and $(2, 0)$. Whenever we're at a point with even $x$-coordinate we have such a binary choice, leading to exponentially many non-crossing hamiltonian paths. $\endgroup$ – Sasho Nikolov Oct 28 '13 at 1:23
  • $\begingroup$ After reading your answer again(many times), and Sasho Nikolov explanation I finally understand what you are saying. And you are right. I am not editing the question to avoid this situation, please tell me if it is yet exponentially many such routes. $\endgroup$ – Ilya Gazman Nov 2 '13 at 11:27

Your Answer

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

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