# Tag Info

36

NP is the class of problems where you can verify "yes" instances. No guarantee is given that you can verify "no" instances. The class of problems where you can verify "no" instances in polynomial time is co-NP. Any language in co-NP is the complement of some language in NP, and vice-versa. Examples include things like non-3-colourability. The problem you ...

30

For 9x9 Sudoku, no. It is finite so can be solved in $O(1)$ time. But if you had a solver for $n^2 \times n^2$ Sudoku, that worked for all $n$ and all possible partial boards, and ran in polynomial time, then yes, that could be used to solve TSP in polynomial time, as completing a $n^2 \times n^2$ Sudoku is NP-complete. The proof of NP-completeness ...

25

It is indeed possible to use a general Sudoku solver to solve instances of TSP, and if this solver takes polynomial time then the whole process will as well (in complexity terminology, there is a polynomial-time reduction from TSP to Sudoku). This is because Sudoku is NP-complete and TSP is in NP. But as is usually the case in this area, looking at the ...

16

Full details are in Robert L. Karg and James L. Thompson, A Heuristic Approach to Solving Traveling Salesman Problems (Management Science, 10(2):225–248, 1964). The PDF is available from JStor and Informs.org (both paywalled). This is the paper that produced the optimal tour of 10,861 miles. It also includes the full distance table but I'll not ...

11

TL;DR: polynomial reduction increases the size of a problem; using a specific solver allows you to exploit the structure of a problem. When you reduce one NP-complete problem to another one, the size of the problem usually grows polynomially. For example, when you reduce a HAMPATH on a graph with $n$ nodes to SAT, the resulting formula has size of $\Theta(n^... 11 If vertices can be visited more than once, then yes: you can create$n+1$copies of the graph, with each vertex$v$in the original graph becoming the$n+1$vertices$v_1, \dots, v_{n+1}$and each edge$uv$in the original graph becoming the set of edges$u_iv_{i+1}$for all$1 \le i \le n$; now run Dijkstra on the resulting graph with start vertex$A_1$and ... 11 First, it's important to recognize the gravity of what you are proposing. If correct, your algorithm is worth$1 Million USD. Secondly, many many people have tried and failed to solve this problem. So it's important to approach this with the assumption that you are wrong, and to exhaustively try to disprove yourself. The next step is to prove two things: ...

8

Most real mazes are trees and there is a polynomial time algorithm for this problem on trees. For ease of description, orient all edges of the tree to point away from the start vertex. Now, for each vertex, delete any child if the subtree rooted at that child contains no vertices that must be visited (i.e., contains no grey or red vertices). The result is a ...

8

What Fiorini et al. show is the following: The TSP polytope $P_n$ over $n$ points is a polytope in $\binom{n}{2}$ dimensions whose vertices correspond to all Hamiltonian cycles in $K_n$ (the complete graph on $n$ vertices). (That is, it is the convex hull of the indicator vectors of all Hamiltonian cycles.) Suppose that $X_n$ is a polytope whose projection ...

7

there are many papers on using artificial neural networks to solve TSP including recurrent and Hopfield networks, and they "succeed" in a rough sense, but so far there does not seem to be any evidence that the techniques are in any way (strongly?) superior to other algorithmic approaches, so its something more like a research curiosity at the moment. the use ...

7

We may reason in a combinatorial way. There are $n!$ permutations of $n$ nodes, but that overcounts the number of tours in two different ways. Since tours are closed, we may start indifferently on any of the $n$ nodes, and we may choose the direction in $2$ ways. Therefore, each tour was counted a total of $2n$ times. This yields the desired result.

7

No, since if every edge has weight 1, there is still the question of whether any such tour exists, which is the Hamiltonian Cycle problem, and this is still NP-hard. (The link is to a Wikipedia page for Hamiltonian Path -- both the path and cycle versions of the problem are hard.)

7

Your conceptual difficulty stems from not distinguishing between TSP and Weighted Hamiltonian Cycle. These are usually discussed as if they are the same problem, but they're not. In Weighted Hamiltonian Cycle, we are given a graph with nonnegative edge weights and we wish to determine the minimum-weight Hamiltonian cycle, i.e., the minimum-weight cycle that ...

6

You missed the footnote — these ways are "not including the connections being identical to a single 2-opt move". Indeed, there are only two permutations in $S_3$ without fixed points (also known as derangements), namely $(123)$ and $(132)$. More generally, for a $k$-opt move it is enough to consider permutations without fixed points, since those with $... 6 This Medium post lists the latest (not a full list of course) studies in the combinatorial optimization domain. All three papers use Deep Reinforcement Learning, which does not need any training set but learns completely from its own experience. I have been working on the first paper for some time and inference time is on milliseconds level. According to ... 6 I think I understand now after trying some examples as Yuval Filmus suggested. In the example below, we can get stuck on the local optimum using 2-opt, but as we can see the global optimum is better. 6 I suggest you read more about the Traveling Salesman Problem. All of your questions are answered in other standard references (such as the Wikipedia link I gave). No, the greedy algorithm is not optimal. You may be interested in the Euclidean TSP, which remains NP-hard. The greedy algorithm is not optimal for that case, either. No efficient algorithm is ... 6 This mostly comes down to what makes an interesting problem, and what can be easily analyzed. The restriction of visiting each vertex once is common in these sorts of problems. A traversal that visits each vertex no more than once is called a "path", and these are well-studied in graph theory, so there are quite a few existing theorems based on them. The ... 5 If$optTSP$is in$NP$, then$coNP = NP$. The latter is unresolved currently. Proof: if$optTSP$is in$NP$, then$coTSP$is in$coNP$(the certificate being whatever certificate was provided to verify a solution to$optTSP$was minimal, and then comparing the value of that solution to the desired bound). And because$TSP$is$NP$-complete then this ... 5 What you're proposing isn't "a linear program for TSP", so it doesn't come into the scope of the proof. You've observed that, if$\mathrm{P=NP}$, then TSP can be reduced to polynomial-sized linear programs. You're using a polynomial-time Turing machine to perform a slightly more complicated version of the following reduction: if the input graph$G$... 4 One can exploit planar separator structures in a geometric setting and thus solve Euclidean TSP exactly in$O(n^{c \sqrt{n}})$time, where$c$is some small constant greater than 1. There's at least three simultaneous results for this; Smith's PhD thesis [1], Kann's PhD thesis [2], and Hwang et al. [3]. Each algorithm has a running time of$O^*(c^{\sqrt{n} \...

4

When we say that TSP is hard to approximate up to a factor $\alpha$, this means that if there was an algorithm for TSP which always outputs a number in $[OPT,\alpha OPT]$ then P=NP (here OPT is the length of the minimal tour). The algorithm doesn't have to find a tour of this length. Even more formally, what these results (probably) show is that there is a ...

4

The worst case running time of Concorde or any other known method is exponential in the size of the input. However, sometimes heuristics or other pruning techniques are effective and you are able to solve some, even large, instances pretty quickly. You should define exactly what you mean by TSP as there are many variants, and many algorithms with different ...

4

I actually found this solution some time ago, but here we go. This is a formulation in a directed graph that can repeat vertices and does not repeat arcs. It requires that for every arc $(i,j)$ there exists an arc $(j,i)$, and that the distance $d_{ij} = d_{ji} \geq 0$. We deal with a directed graph $G = (V, A)$. For $W \subseteq V$, we define $\delta^-(W) =... 4 This is directly equivalent to metric TSP. That is, TSP in which the distances obey the triangle inequality: for all cities$A$,$B$and$C$, the distance from$A$to$B$is no greater than the distance from$A$to$C$to$B$. As Raphael points oun in the comments, you can reduce an instance of your problem to metric TSP by setting the ... 4 You're confusing a polynomial time approximation scheme (PTAS) and a fully polynomial time approximation scheme (FPTAS). Euclidean TSP has a PTAS, but it is not an FPTAS because the polynomial increases in degree as 1 / ε decreases. Only an FPTAS is disallowed for strongly NP-hard problems, assuming P$\neq$NP. 4 There is a lot of freedom in the algorithm: several minimum spanning trees, and several corresponding Eulerian tours. Try to find the worst choice and show that it produces an inferior tour. What you are showing is that the algorithm could make this choice, and so could produce an inferior approximation. If you don't like this idea of choice, you can ... 4 The Traveling Salesman Problem (TSP) is a classic problem because it's hard to deterministically solve in a decent time frame, classified as NP-hard. Genetic algorithms can get a good solution more quickly than NP-hard time, but there's no guarantee that you'll find an actual optimal solution. This can be a good trade-off if you're programming, say, a ... 4 there are almost no other information regarding this algorithm online [...] I would really appreciate a pseudo-code, if anyone has ever implemented this algorithm. I invite you to read my paper "An Empirical Study of the Multi-fragment Tour Construction Algorithm for the Travelling Salesman Problem" appeared in the Proceedings of the 16th International ... 4 Grid graphs are finite node-induced graphs of the infinite planar grid (whose vertices are integral points, and two vertices are linked when their Euclidean distance is 1). A. Itai, C. H. Papadimitriou, and J. L. Szwarcfiter proved that the Hamiltonian path problem on grid graphs is NP-complete. To reduce that to your problem, suppose the grid graph has$m\$ ...

Only top voted, non community-wiki answers of a minimum length are eligible