Skip to main content
36 votes
Accepted

How is the traveling salesman problem verifiable in polynomial time?

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 ...
David Richerby's user avatar
30 votes
Accepted

If I can solve Sudoku, can I solve the Travelling Salesman Problem (TSP)? If so, how?

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 ...
D.W.'s user avatar
  • 162k
25 votes

If I can solve Sudoku, can I solve the Travelling Salesman Problem (TSP)? If so, how?

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 ...
rlms's user avatar
  • 520
13 votes
Accepted

Why the need for TSP solvers when there are SAT solvers?

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 ...
Ivan Smirnov's user avatar
11 votes
Accepted

Shortest path between two points with n hops

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 ...
j_random_hacker's user avatar
11 votes
Accepted

Traveling Salesman Solution

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 ...
Joey Eremondi's user avatar
8 votes
Accepted

Why does this not prove $P\neq NP$?

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 ...
Yuval Filmus's user avatar
8 votes
Accepted

Is there an efficient solution to the travelling salesman problem with binary edge weights?

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 ...
j_random_hacker's user avatar
8 votes

For what applications of the traveling salesman problem, does visiting each city at most once truely matter?

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 ...
David Richerby's user avatar
7 votes
Accepted

Show that there are $(n-1)!/2$ distinct tours for a Euclidean traveling salesman problem on $n$ points?

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 ...
quicksort's user avatar
  • 4,272
7 votes
Accepted

Traveling Salesman Problem with Neural Network

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 ...
tahsin kose's user avatar
6 votes
Accepted

Has it been proven that the optimization TSP is (or is not) polynomial-time verifiable if P ≠ NP?

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 ...
Scrub's user avatar
  • 76
6 votes
Accepted

Why doesn't 2-opt return an optimal solution?

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.
J. Schmidt's user avatar
6 votes

What if the travelling salesman travelled by plane?

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 ...
D.W.'s user avatar
  • 162k
6 votes
Accepted

Why does Travelling Salesman Problem pose the restriction that each vertex can only be visited once?

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 ...
Draconis's user avatar
  • 7,148
5 votes

Why does this not prove $P\neq NP$?

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 ...
David Richerby's user avatar
4 votes

Implement multi-fragment heuristics for the traveling salesman problem

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 "...
elkrari's user avatar
  • 71
4 votes

How to simulate a parallel computer (with certain number of processors) on a serial computer

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 ...
Nat's user avatar
  • 1,351
4 votes
Accepted

Rearranging strings so that the Hamming distance between them is 1

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. ...
Wei Zhan's user avatar
  • 1,183
4 votes
Accepted

How to prove non-existence of $O(2^n)$ approximation algorithm solving TSP?

After @YuvalFilmus' hint it turns out the answer lies in this book. The TSP can be used to solve the Hamiltonian Cycle problem by creating a new graph as following. Given $\alpha > 1$ and a graph $...
HardFork's user avatar
  • 534
4 votes

Linear Path Optimization with Two Dependent Variables

You can consider the 1D-position of the 2 runners as one 2D-position. X-coordinate and Y-coordinate for respectively runners 1 and 2. So in your instance, the starting point is (0, 100). Then all ...
Optidad's user avatar
  • 1,788
4 votes
Accepted

Standard ILP Formulation of Travelling salesman problem: Purpose of subtour elimination constraints?

Consider this example: Every vertex has one incoming and one outgoing edge, so it is not prevented by the first two constraints. It is however prevented by the third constraint, as if you take any of ...
Tassle's user avatar
  • 2,522
4 votes
Accepted

Space complexity of Travelling Salesman Problem

The brute force solution enumerates all permutations. You can easily encode each permutation using $n\log n$ bits, since you can encode it as a list of numbers from $1$ to $n$, and each number takes $\...
Yuval Filmus's user avatar
4 votes
Accepted

Approximation concerning Asymmetric TSP, Symmetric TSP, and Metric TSP

Here is an excerpt from the introduction to an earlier paper of Svensson, Tarnawski and Végh, which was the first to give a constant factor approximation algorithm for ATSP: Without any assumptions ...
Yuval Filmus's user avatar
4 votes

What is the shortest total path between pairs of points?

This appears to be a maximum matching problem. Well, minimum matching, but you should be able to make the necessary adaptations.
D.W.'s user avatar
  • 162k
4 votes

How to prove that this problem is NP Complete

Same class last semester: an edge between two vertices. Students in a circle: an hamiltonian cycle. I think you should be able to do the rest.
Nathaniel's user avatar
  • 15.8k
3 votes

Is a two-opt move guaranteed to produce a non-worse tour?

2-Opt is a move that doesn't guarantee to give a better tour. We use such moves ($k$-Opt, swap, insertion,..) in local searches to look for a better tour in the neighbor of the input (which is a tour)...
elkrari's user avatar
  • 71
3 votes

Traveling Salesman Problem with Neural Network

I commented this on another answer, but I think it deserves its own answer. Some Google Brain fellows presented a method for solving TSP using an architecture reminiscent of seq2seq in the 2017 paper ...
Sam H.'s user avatar
  • 131
3 votes
Accepted

Traveling Salesman -- number of qubits required?

The notebook describes how to solve combinatorial optimization problems by encoding them as minimizing a binary quadratic form, which can in turn be phrased as finding the minimal eigenvalue of a ...
Yuval Filmus's user avatar
3 votes

Traveling salesman problem with disconnected cities / infinite length edge

You're just trying to find Hamiltonian cycles in unweighted graphs. That's still NP-complete. If you want to do it with a TSP solver, do it as follows. Suppose you have a graph on $n$ vertices. ...
David Richerby's user avatar

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