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

34

The crux is that you have to consider the decision problem: Travelling Salesman Problem (Decision Version). Given a weighted graph G and a target cost C, is there a Hamiltonian cycle in G whose weight is at most C? For a 'yes' instance, the certificate is just some Hamiltonian cycle whose weight is at most C. If you could solve this problem efficiently, ...

32

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

26

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

20

To be more precise, we do not know if TSP is in $\mathsf{P}$. It is possible that it can be solved in polynomial time, even though perhaps the common belief is that $\mathsf{P} \neq \mathsf{NP}$. Now, recall what it means for a problem to be $\mathsf{NP}$-hard and $\mathsf{NP}$-complete, see for example my answer here. I believe your source of confusion ...

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

10

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

10

I'm assuming that you're thinking of the Euclidean traveling salesman problem, where $c$ and $v$ are vectors in $\mathbb{Z}^{2n}$, with two coordinates for each city. Let $minTSP(c)$ denote the length of the minimum traveling salesman tour for the cities with coordinates $c$. Then your problem asks whether $$minTSP(c + v) \ge min TSP(c) + x.$$ But then ...

10

For asymptotic bounds, Fiorini, Massar, Pokutta, Tiwari, and de Wolf recently showed exponential lower bounds on the number of facets of any polytope that projects to the TSP polytope (the TSP polytope, being the convex hull of feasible TSP solutions). This is stronger than what you ask for, and implies that even adding extra variables will not make the TSP ...

7

Consider a ladder a----b----c | | | d----e----f Say length of a-b is $2$ and length of a-d is $1$. The optimal route is a-b-c-f-e-d-a, $10$ units long. Starting at a, NN would produce a-d-e-b-c-f-a which is $7 + \sqrt{17} > 11$ units long. There is actually a four node example, a rhombus A /|\ B-+-C \|/ D Say length of B-C is $10$, length ...

7

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

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

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 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 ... 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 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 ... 5 Here is what these lecture notes have to say. We can reduce HAMILTONIAN-PATH to MIN-TSP-TOUR in the following way: give the weight$1$for edges in the original graph, and$B$(for some$B > 1$to be chosen later) for edges not in the original graph. If the original graph had a Hamiltonian path, then the new path has a tour of length at most$n$, and ... 5 As a simple method, you can use the roulette wheel selection. The idea is that every individual has a chance to be selected as a parent, but the more fit an individual is, the more likely it is to be selected. Let$f_i$be the fitness of the individual$i$. The probability$p_i$of choosing$i$as a parent for the next round is$p_i = f_i / \sum_{j=1}^{N}$, ... 5 There are a few good books on the TSP problem where you are likely to find some relevant information: Lawler et al., eds. The traveling salesman problem: A guided tour of combinatorial optimization. Wiley, 1985. G. Reinelt. The traveling salesman: computational solutions for TSP applications. Springer, 1994. G. Gutin and A. P. Punnen, eds. The traveling ... 5 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. 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\$ ...

5

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

4

There is a library called SMAPO (short for library of linear descriptions of SMAll problem instances of POlytopes in combinatorial optimization) for a lot of polytopes including the symmetric TVP as well as the graphical TSP. For the STSP, this is the list of number of facets for small polytopes Nodes in STSP | # of facets ----------------+-------------...

4

Hint: Every TSP tour has the same number of edges. Use this to modify the weights in the graph in a way which affects all TSP tours in the same way.

4

If the edges don't satisfy the triangle inequality then the problem becomes harder. In your case the non-edges have infinite weight (since you want never to use them), so you can't expect Christofides' algorithm to be useful as such.

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