Is there an efficient solution to the travelling salesman problem with binary edge weights? Planned maintenance scheduled April 23, 2019 at 23:30 UTC (7:30pm US/Eastern) Announcing the arrival of Valued Associate #679: Cesar Manara Unicorn Meta Zoo #1: Why another podcast?How can I verify a solution to Travelling Salesman Problem in polynomial time?Travelling salesman problem with detoursEvolutionary algorithm for the Physical Travelling Salesman ProblemTravelling Salesman Problem with unknown shortest paths between nodesWhat if the travelling salesman travelled by plane?Traveling salesman problem with disconnected cities / infinite length edgeTravelling salesman problem with small edge weightsWhy does Travelling Salesman Problem pose the restriction that each vertex can only be visited once?Travelling Salesman problem using Guided Local SearchIf I can solve Sudoku, can I solve the Travelling Salesman Problem (TSP)? If so, how?
NIntegrate on a solution of a matrix ODE
Sally's older brother
Centre cell vertically in tabularx
Why not use the yoke to control yaw, as well as pitch and roll?
Inverse square law not accurate for non-point masses?
Are there any irrational/transcendental numbers for which the distribution of decimal digits is not uniform?
Is this Kuo-toa homebrew race balanced?
3D Masyu - A Die
Can two people see the same photon?
Does the universe have a fixed centre of mass?
Weaponising the Grasp-at-a-Distance spell
How do you write "wild blueberries flavored"?
Relating to the President and obstruction, were Mueller's conclusions preordained?
Is the time—manner—place ordering of adverbials an oversimplification?
2018 MacBook Pro won't let me install macOS High Sierra 10.13 from USB installer
Twin's vs. Twins'
Is it OK to use the testing sample to compare algorithms?
Short story about astronauts fertilizing soil with their own bodies
Releasing Patch File for BSD3 Licensed Project
Why are two-digit numbers in Jonathan Swift's "Gulliver's Travels" (1726) written in "German style"?
Any stored/leased 737s that could substitute for grounded MAXs?
Determine whether an integer is a palindrome
When does a function NOT have an antiderivative?
The test team as an enemy of development? And how can this be avoided?
Is there an efficient solution to the travelling salesman problem with binary edge weights?
Planned maintenance scheduled April 23, 2019 at 23:30 UTC (7:30pm US/Eastern)
Announcing the arrival of Valued Associate #679: Cesar Manara
Unicorn Meta Zoo #1: Why another podcast?How can I verify a solution to Travelling Salesman Problem in polynomial time?Travelling salesman problem with detoursEvolutionary algorithm for the Physical Travelling Salesman ProblemTravelling Salesman Problem with unknown shortest paths between nodesWhat if the travelling salesman travelled by plane?Traveling salesman problem with disconnected cities / infinite length edgeTravelling salesman problem with small edge weightsWhy does Travelling Salesman Problem pose the restriction that each vertex can only be visited once?Travelling Salesman problem using Guided Local SearchIf I can solve Sudoku, can I solve the Travelling Salesman Problem (TSP)? If so, how?
$begingroup$
Is there a way to solve TSP in polynomial time if there are only two kinds of weights, 0 and 1?
traveling-salesman
edited Mar 24 at 11:13
Apass.Jack
14.4k1940
asked Mar 24 at 7:33
WiccanKarnakWiccanKarnak
1185
$endgroup$
add a comment |
$begingroup$
Is there a way to solve TSP in polynomial time if there are only two kinds of weights, 0 and 1?
traveling-salesman
edited Mar 24 at 11:13
Apass.Jack
14.4k1940
asked Mar 24 at 7:33
WiccanKarnakWiccanKarnak
1185
$endgroup$
add a comment |
$begingroup$
Is there a way to solve TSP in polynomial time if there are only two kinds of weights, 0 and 1?
traveling-salesman
edited Mar 24 at 11:13
Apass.Jack
14.4k1940
asked Mar 24 at 7:33
WiccanKarnakWiccanKarnak
1185
$endgroup$
Is there a way to solve TSP in polynomial time if there are only two kinds of weights, 0 and 1?
traveling-salesman
traveling-salesman
edited Mar 24 at 11:13
Apass.Jack
14.4k1940
asked Mar 24 at 7:33
WiccanKarnakWiccanKarnak
1185
edited Mar 24 at 11:13
Apass.Jack
14.4k1940
asked Mar 24 at 7:33
WiccanKarnakWiccanKarnak
1185
edited Mar 24 at 11:13
Apass.Jack
14.4k1940
edited Mar 24 at 11:13
Apass.Jack
14.4k1940
edited Mar 24 at 11:13
Apass.Jack
14.4k1940
14.4k1940
asked Mar 24 at 7:33
WiccanKarnakWiccanKarnak
1185
asked Mar 24 at 7:33
WiccanKarnakWiccanKarnak
1185
asked Mar 24 at 7:33
WiccanKarnakWiccanKarnak
1185
1185
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
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.)
answered Mar 24 at 8:39
j_random_hackerj_random_hacker
3,02711016
$endgroup$
3
$begingroup$
I initially read the question with the assumption it's asking about complete graphs - but then you can still get the Hamiltonian Cycle problem by asking if a zero-length Hamiltonian cycle exists. And if you allow retrace, the problem becomes trivial.
$endgroup$
– John Dvorak
Mar 24 at 11:16
$begingroup$
@JohnDvorak thanks a lot, is there a way if I guarantee no Hamiltonian Cycles?
$endgroup$
– WiccanKarnak
Mar 24 at 14:43
$begingroup$
Every complete graph has a Hamiltonian cycle. And if your graph doesn't have a Hamiltonian cycle ... then it definitely doesn't have a Hamiltonian cycle, so what was the question again?
$endgroup$
– John Dvorak
Mar 24 at 15:00
$begingroup$
@WiccanKarnak : (A TSP solution is a Hamiltonian cycle ... of minimal total weight.)
$endgroup$
– Eric Towers
Mar 24 at 19:39
$begingroup$
Aren't you allowed to use the same edge twice in TSP?
$endgroup$
– immibis
Mar 24 at 22:00
|
show 1 more comment
$begingroup$
The accepted answer isn't quite right. An instance of TSP consists of a distance between every pair of cities: that is, it consists of a weighted complete graph. Every complete graph has a Hamiltonian cycle.
However, it is simple to reduce HAMILTON-CYCLE to $0$–$1$ TSP. Given a graph $G$, create a TSP instance where the cities are the vertices and the distance is $0$ if there is an edge between the cities and $1$ if there is not. Then $G$ has a Hamiltonian cyle if, and only if, the TSP instance has a tour of weight zero. Therefore, $0$–$1$ TSP is NP-complete.
answered Mar 24 at 20:20
David RicherbyDavid Richerby
70.8k16108198
$endgroup$
$begingroup$
This is a good point, though the choice of whether to require the input graph to be complete or not never makes a practical difference (for the purpose of finding a distance-minimal tour, missing edges in a graph can be encoded as arbitrarily-distant edges in a complete graph). Interestingly, in looking for a definitively canonical definition of the TSP problem, I found that on p. 211 of Garey & Johnson (1979) they require the edge weights to be in $mathbb Z^+$ -- i.e., 0-length edges are forbidden, meaning that for them, the "0-1 TSP" described here is technically not a special case of TSP!
$endgroup$
– j_random_hacker
Mar 25 at 11:24
$begingroup$
@j_random_hacker It's a good job I'm only throwing small stones in my glass house! (Actually, you can reduce $0$-$1$ TSP to $1$-$2$ TSP by just adding one to every edge weight and adding $n$ to the length of the path you're looking for.)
$endgroup$
– David Richerby
Mar 25 at 11:29
add a comment |
Your Answer
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "419"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f105984%2fis-there-an-efficient-solution-to-the-travelling-salesman-problem-with-binary-ed%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
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.)
answered Mar 24 at 8:39
j_random_hackerj_random_hacker
3,02711016
$endgroup$
3
$begingroup$
I initially read the question with the assumption it's asking about complete graphs - but then you can still get the Hamiltonian Cycle problem by asking if a zero-length Hamiltonian cycle exists. And if you allow retrace, the problem becomes trivial.
$endgroup$
– John Dvorak
Mar 24 at 11:16
$begingroup$
@JohnDvorak thanks a lot, is there a way if I guarantee no Hamiltonian Cycles?
$endgroup$
– WiccanKarnak
Mar 24 at 14:43
$begingroup$
Every complete graph has a Hamiltonian cycle. And if your graph doesn't have a Hamiltonian cycle ... then it definitely doesn't have a Hamiltonian cycle, so what was the question again?
$endgroup$
– John Dvorak
Mar 24 at 15:00
$begingroup$
@WiccanKarnak : (A TSP solution is a Hamiltonian cycle ... of minimal total weight.)
$endgroup$
– Eric Towers
Mar 24 at 19:39
$begingroup$
Aren't you allowed to use the same edge twice in TSP?
$endgroup$
– immibis
Mar 24 at 22:00
|
show 1 more comment
$begingroup$
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.)
answered Mar 24 at 8:39
j_random_hackerj_random_hacker
3,02711016
$endgroup$
3
$begingroup$
I initially read the question with the assumption it's asking about complete graphs - but then you can still get the Hamiltonian Cycle problem by asking if a zero-length Hamiltonian cycle exists. And if you allow retrace, the problem becomes trivial.
$endgroup$
– John Dvorak
Mar 24 at 11:16
$begingroup$
@JohnDvorak thanks a lot, is there a way if I guarantee no Hamiltonian Cycles?
$endgroup$
– WiccanKarnak
Mar 24 at 14:43
$begingroup$
Every complete graph has a Hamiltonian cycle. And if your graph doesn't have a Hamiltonian cycle ... then it definitely doesn't have a Hamiltonian cycle, so what was the question again?
$endgroup$
– John Dvorak
Mar 24 at 15:00
$begingroup$
@WiccanKarnak : (A TSP solution is a Hamiltonian cycle ... of minimal total weight.)
$endgroup$
– Eric Towers
Mar 24 at 19:39
$begingroup$
Aren't you allowed to use the same edge twice in TSP?
$endgroup$
– immibis
Mar 24 at 22:00
|
show 1 more comment
$begingroup$
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.)
answered Mar 24 at 8:39
j_random_hackerj_random_hacker
3,02711016
$endgroup$
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.)
answered Mar 24 at 8:39
j_random_hackerj_random_hacker
3,02711016
answered Mar 24 at 8:39
j_random_hackerj_random_hacker
3,02711016
answered Mar 24 at 8:39
j_random_hackerj_random_hacker
3,02711016
answered Mar 24 at 8:39
j_random_hackerj_random_hacker
3,02711016
3,02711016
3
$begingroup$
I initially read the question with the assumption it's asking about complete graphs - but then you can still get the Hamiltonian Cycle problem by asking if a zero-length Hamiltonian cycle exists. And if you allow retrace, the problem becomes trivial.
$endgroup$
– John Dvorak
Mar 24 at 11:16
$begingroup$
@JohnDvorak thanks a lot, is there a way if I guarantee no Hamiltonian Cycles?
$endgroup$
– WiccanKarnak
Mar 24 at 14:43
$begingroup$
Every complete graph has a Hamiltonian cycle. And if your graph doesn't have a Hamiltonian cycle ... then it definitely doesn't have a Hamiltonian cycle, so what was the question again?
$endgroup$
– John Dvorak
Mar 24 at 15:00
$begingroup$
@WiccanKarnak : (A TSP solution is a Hamiltonian cycle ... of minimal total weight.)
$endgroup$
– Eric Towers
Mar 24 at 19:39
$begingroup$
Aren't you allowed to use the same edge twice in TSP?
$endgroup$
– immibis
Mar 24 at 22:00
|
show 1 more comment
3
$begingroup$
I initially read the question with the assumption it's asking about complete graphs - but then you can still get the Hamiltonian Cycle problem by asking if a zero-length Hamiltonian cycle exists. And if you allow retrace, the problem becomes trivial.
$endgroup$
– John Dvorak
Mar 24 at 11:16
$begingroup$
@JohnDvorak thanks a lot, is there a way if I guarantee no Hamiltonian Cycles?
$endgroup$
– WiccanKarnak
Mar 24 at 14:43
$begingroup$
Every complete graph has a Hamiltonian cycle. And if your graph doesn't have a Hamiltonian cycle ... then it definitely doesn't have a Hamiltonian cycle, so what was the question again?
$endgroup$
– John Dvorak
Mar 24 at 15:00
$begingroup$
@WiccanKarnak : (A TSP solution is a Hamiltonian cycle ... of minimal total weight.)
$endgroup$
– Eric Towers
Mar 24 at 19:39
$begingroup$
Aren't you allowed to use the same edge twice in TSP?
$endgroup$
– immibis
Mar 24 at 22:00
3
3
$begingroup$
I initially read the question with the assumption it's asking about complete graphs - but then you can still get the Hamiltonian Cycle problem by asking if a zero-length Hamiltonian cycle exists. And if you allow retrace, the problem becomes trivial.
$endgroup$
– John Dvorak
Mar 24 at 11:16
$begingroup$
I initially read the question with the assumption it's asking about complete graphs - but then you can still get the Hamiltonian Cycle problem by asking if a zero-length Hamiltonian cycle exists. And if you allow retrace, the problem becomes trivial.
$endgroup$
– John Dvorak
Mar 24 at 11:16
$begingroup$
@JohnDvorak thanks a lot, is there a way if I guarantee no Hamiltonian Cycles?
$endgroup$
– WiccanKarnak
Mar 24 at 14:43
$begingroup$
@JohnDvorak thanks a lot, is there a way if I guarantee no Hamiltonian Cycles?
$endgroup$
– WiccanKarnak
Mar 24 at 14:43
$begingroup$
Every complete graph has a Hamiltonian cycle. And if your graph doesn't have a Hamiltonian cycle ... then it definitely doesn't have a Hamiltonian cycle, so what was the question again?
$endgroup$
– John Dvorak
Mar 24 at 15:00
$begingroup$
Every complete graph has a Hamiltonian cycle. And if your graph doesn't have a Hamiltonian cycle ... then it definitely doesn't have a Hamiltonian cycle, so what was the question again?
$endgroup$
– John Dvorak
Mar 24 at 15:00
$begingroup$
@WiccanKarnak : (A TSP solution is a Hamiltonian cycle ... of minimal total weight.)
$endgroup$
– Eric Towers
Mar 24 at 19:39
$begingroup$
@WiccanKarnak : (A TSP solution is a Hamiltonian cycle ... of minimal total weight.)
$endgroup$
– Eric Towers
Mar 24 at 19:39
$begingroup$
Aren't you allowed to use the same edge twice in TSP?
$endgroup$
– immibis
Mar 24 at 22:00
$begingroup$
Aren't you allowed to use the same edge twice in TSP?
$endgroup$
– immibis
Mar 24 at 22:00
|
show 1 more comment
$begingroup$
The accepted answer isn't quite right. An instance of TSP consists of a distance between every pair of cities: that is, it consists of a weighted complete graph. Every complete graph has a Hamiltonian cycle.
However, it is simple to reduce HAMILTON-CYCLE to $0$–$1$ TSP. Given a graph $G$, create a TSP instance where the cities are the vertices and the distance is $0$ if there is an edge between the cities and $1$ if there is not. Then $G$ has a Hamiltonian cyle if, and only if, the TSP instance has a tour of weight zero. Therefore, $0$–$1$ TSP is NP-complete.
answered Mar 24 at 20:20
David RicherbyDavid Richerby
70.8k16108198
$endgroup$
$begingroup$
This is a good point, though the choice of whether to require the input graph to be complete or not never makes a practical difference (for the purpose of finding a distance-minimal tour, missing edges in a graph can be encoded as arbitrarily-distant edges in a complete graph). Interestingly, in looking for a definitively canonical definition of the TSP problem, I found that on p. 211 of Garey & Johnson (1979) they require the edge weights to be in $mathbb Z^+$ -- i.e., 0-length edges are forbidden, meaning that for them, the "0-1 TSP" described here is technically not a special case of TSP!
$endgroup$
– j_random_hacker
Mar 25 at 11:24
$begingroup$
@j_random_hacker It's a good job I'm only throwing small stones in my glass house! (Actually, you can reduce $0$-$1$ TSP to $1$-$2$ TSP by just adding one to every edge weight and adding $n$ to the length of the path you're looking for.)
$endgroup$
– David Richerby
Mar 25 at 11:29
add a comment |
$begingroup$
The accepted answer isn't quite right. An instance of TSP consists of a distance between every pair of cities: that is, it consists of a weighted complete graph. Every complete graph has a Hamiltonian cycle.
However, it is simple to reduce HAMILTON-CYCLE to $0$–$1$ TSP. Given a graph $G$, create a TSP instance where the cities are the vertices and the distance is $0$ if there is an edge between the cities and $1$ if there is not. Then $G$ has a Hamiltonian cyle if, and only if, the TSP instance has a tour of weight zero. Therefore, $0$–$1$ TSP is NP-complete.
answered Mar 24 at 20:20
David RicherbyDavid Richerby
70.8k16108198
$endgroup$
$begingroup$
This is a good point, though the choice of whether to require the input graph to be complete or not never makes a practical difference (for the purpose of finding a distance-minimal tour, missing edges in a graph can be encoded as arbitrarily-distant edges in a complete graph). Interestingly, in looking for a definitively canonical definition of the TSP problem, I found that on p. 211 of Garey & Johnson (1979) they require the edge weights to be in $mathbb Z^+$ -- i.e., 0-length edges are forbidden, meaning that for them, the "0-1 TSP" described here is technically not a special case of TSP!
$endgroup$
– j_random_hacker
Mar 25 at 11:24
$begingroup$
@j_random_hacker It's a good job I'm only throwing small stones in my glass house! (Actually, you can reduce $0$-$1$ TSP to $1$-$2$ TSP by just adding one to every edge weight and adding $n$ to the length of the path you're looking for.)
$endgroup$
– David Richerby
Mar 25 at 11:29
add a comment |
$begingroup$
The accepted answer isn't quite right. An instance of TSP consists of a distance between every pair of cities: that is, it consists of a weighted complete graph. Every complete graph has a Hamiltonian cycle.
However, it is simple to reduce HAMILTON-CYCLE to $0$–$1$ TSP. Given a graph $G$, create a TSP instance where the cities are the vertices and the distance is $0$ if there is an edge between the cities and $1$ if there is not. Then $G$ has a Hamiltonian cyle if, and only if, the TSP instance has a tour of weight zero. Therefore, $0$–$1$ TSP is NP-complete.
answered Mar 24 at 20:20
David RicherbyDavid Richerby
70.8k16108198
$endgroup$
The accepted answer isn't quite right. An instance of TSP consists of a distance between every pair of cities: that is, it consists of a weighted complete graph. Every complete graph has a Hamiltonian cycle.
However, it is simple to reduce HAMILTON-CYCLE to $0$–$1$ TSP. Given a graph $G$, create a TSP instance where the cities are the vertices and the distance is $0$ if there is an edge between the cities and $1$ if there is not. Then $G$ has a Hamiltonian cyle if, and only if, the TSP instance has a tour of weight zero. Therefore, $0$–$1$ TSP is NP-complete.
answered Mar 24 at 20:20
David RicherbyDavid Richerby
70.8k16108198
answered Mar 24 at 20:20
David RicherbyDavid Richerby
70.8k16108198
answered Mar 24 at 20:20
David RicherbyDavid Richerby
70.8k16108198
answered Mar 24 at 20:20
David RicherbyDavid Richerby
70.8k16108198
70.8k16108198
$begingroup$
This is a good point, though the choice of whether to require the input graph to be complete or not never makes a practical difference (for the purpose of finding a distance-minimal tour, missing edges in a graph can be encoded as arbitrarily-distant edges in a complete graph). Interestingly, in looking for a definitively canonical definition of the TSP problem, I found that on p. 211 of Garey & Johnson (1979) they require the edge weights to be in $mathbb Z^+$ -- i.e., 0-length edges are forbidden, meaning that for them, the "0-1 TSP" described here is technically not a special case of TSP!
$endgroup$
– j_random_hacker
Mar 25 at 11:24
$begingroup$
@j_random_hacker It's a good job I'm only throwing small stones in my glass house! (Actually, you can reduce $0$-$1$ TSP to $1$-$2$ TSP by just adding one to every edge weight and adding $n$ to the length of the path you're looking for.)
$endgroup$
– David Richerby
Mar 25 at 11:29
add a comment |
$begingroup$
This is a good point, though the choice of whether to require the input graph to be complete or not never makes a practical difference (for the purpose of finding a distance-minimal tour, missing edges in a graph can be encoded as arbitrarily-distant edges in a complete graph). Interestingly, in looking for a definitively canonical definition of the TSP problem, I found that on p. 211 of Garey & Johnson (1979) they require the edge weights to be in $mathbb Z^+$ -- i.e., 0-length edges are forbidden, meaning that for them, the "0-1 TSP" described here is technically not a special case of TSP!
$endgroup$
– j_random_hacker
Mar 25 at 11:24
$begingroup$
@j_random_hacker It's a good job I'm only throwing small stones in my glass house! (Actually, you can reduce $0$-$1$ TSP to $1$-$2$ TSP by just adding one to every edge weight and adding $n$ to the length of the path you're looking for.)
$endgroup$
– David Richerby
Mar 25 at 11:29
$begingroup$
This is a good point, though the choice of whether to require the input graph to be complete or not never makes a practical difference (for the purpose of finding a distance-minimal tour, missing edges in a graph can be encoded as arbitrarily-distant edges in a complete graph). Interestingly, in looking for a definitively canonical definition of the TSP problem, I found that on p. 211 of Garey & Johnson (1979) they require the edge weights to be in $mathbb Z^+$ -- i.e., 0-length edges are forbidden, meaning that for them, the "0-1 TSP" described here is technically not a special case of TSP!
$endgroup$
– j_random_hacker
Mar 25 at 11:24
$begingroup$
This is a good point, though the choice of whether to require the input graph to be complete or not never makes a practical difference (for the purpose of finding a distance-minimal tour, missing edges in a graph can be encoded as arbitrarily-distant edges in a complete graph). Interestingly, in looking for a definitively canonical definition of the TSP problem, I found that on p. 211 of Garey & Johnson (1979) they require the edge weights to be in $mathbb Z^+$ -- i.e., 0-length edges are forbidden, meaning that for them, the "0-1 TSP" described here is technically not a special case of TSP!
$endgroup$
– j_random_hacker
Mar 25 at 11:24
$begingroup$
@j_random_hacker It's a good job I'm only throwing small stones in my glass house! (Actually, you can reduce $0$-$1$ TSP to $1$-$2$ TSP by just adding one to every edge weight and adding $n$ to the length of the path you're looking for.)
$endgroup$
– David Richerby
Mar 25 at 11:29
$begingroup$
@j_random_hacker It's a good job I'm only throwing small stones in my glass house! (Actually, you can reduce $0$-$1$ TSP to $1$-$2$ TSP by just adding one to every edge weight and adding $n$ to the length of the path you're looking for.)
$endgroup$
– David Richerby
Mar 25 at 11:29
add a comment |
Thanks for contributing an answer to Computer Science Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f105984%2fis-there-an-efficient-solution-to-the-travelling-salesman-problem-with-binary-ed%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
