Proof that shortest path with negative cycles is NP hard
Do simulator games use a realistic trajectory to get into orbit?
Why only the fundamental frequency component is said to give useful power?
How many pairs of subsets can be formed?
Building a road to escape Earth's gravity by making a pyramid on Antartica
Turing patterns
Is any name of Vishnu Siva?
Is it possible to (7 day) schedule sleep time of a hard drive?
How is it possible that Gollum speaks Westron?
Do the English have an ancient (obsolete) verb for the action of the book opening?
Did thousands of women die every year due to illegal abortions before Roe v. Wade?
Are there any existing monsters I can use as a basis for a baby skeleton statblock?
Average spam confidence
My coworkers think I had a long honeymoon. Actually I was diagnosed with cancer. How do I talk about it?
How can you travel on a trans-Siberian train when it is fully booked?
Can an Eldritch Knight use Action Surge and thus Arcane Charge even when surprised?
Do any instruments not produce overtones?
How do photons get into the eyes?
After the loss of Challenger, why weren’t Galileo and Ulysses launched by Centaurs on expendable boosters?
Pushout commutative diagram
Where does this pattern of naming products come from?
Why is the application of an oracle function not a measurement?
How many times can you cast a card exiled by Release to the Wind?
Why does the Schrödinger equation work so well for the Hydrogen atom despite the relativistic boundary at the nucleus?
Last survivors from different time periods living together
Proof that shortest path with negative cycles is NP hard
$begingroup$
I'm looking into the shortest path problem and am wondering how to prove that shortest path with neg. cycles is NP-hard. (Or is it NPC? Is there a way to validate in P time that the path really is shortest?)
How would I reduce the SAT problem into the shortest path problem in polynomial time?
graph-theory shortest-path
asked 15 hours ago
Tin ManTin Man
1235
$endgroup$
add a comment |
$begingroup$
I'm looking into the shortest path problem and am wondering how to prove that shortest path with neg. cycles is NP-hard. (Or is it NPC? Is there a way to validate in P time that the path really is shortest?)
How would I reduce the SAT problem into the shortest path problem in polynomial time?
graph-theory shortest-path
asked 15 hours ago
Tin ManTin Man
1235
$endgroup$
2
$begingroup$
Do you have to reduce from SAT? A simple reduction is from Hamiltonian path.
$endgroup$
– Juho
14 hours ago
$begingroup$
The decision version of your problem is: Given a graph and a number $ell$, is there a path whose length is shorter than $ell$? This is clearly in NP.
$endgroup$
– Yuval Filmus
6 hours ago
add a comment |
$begingroup$
I'm looking into the shortest path problem and am wondering how to prove that shortest path with neg. cycles is NP-hard. (Or is it NPC? Is there a way to validate in P time that the path really is shortest?)
How would I reduce the SAT problem into the shortest path problem in polynomial time?
graph-theory shortest-path
asked 15 hours ago
Tin ManTin Man
1235
$endgroup$
I'm looking into the shortest path problem and am wondering how to prove that shortest path with neg. cycles is NP-hard. (Or is it NPC? Is there a way to validate in P time that the path really is shortest?)
How would I reduce the SAT problem into the shortest path problem in polynomial time?
graph-theory shortest-path
graph-theory shortest-path
asked 15 hours ago
Tin ManTin Man
1235
asked 15 hours ago
Tin ManTin Man
1235
asked 15 hours ago
Tin ManTin Man
1235
asked 15 hours ago
Tin ManTin Man
1235
asked 15 hours ago
Tin ManTin Man
1235
1235
2
$begingroup$
Do you have to reduce from SAT? A simple reduction is from Hamiltonian path.
$endgroup$
– Juho
14 hours ago
$begingroup$
The decision version of your problem is: Given a graph and a number $ell$, is there a path whose length is shorter than $ell$? This is clearly in NP.
$endgroup$
– Yuval Filmus
6 hours ago
add a comment |
2
$begingroup$
Do you have to reduce from SAT? A simple reduction is from Hamiltonian path.
$endgroup$
– Juho
14 hours ago
$begingroup$
The decision version of your problem is: Given a graph and a number $ell$, is there a path whose length is shorter than $ell$? This is clearly in NP.
$endgroup$
– Yuval Filmus
6 hours ago
2
2
$begingroup$
Do you have to reduce from SAT? A simple reduction is from Hamiltonian path.
$endgroup$
– Juho
14 hours ago
$begingroup$
Do you have to reduce from SAT? A simple reduction is from Hamiltonian path.
$endgroup$
– Juho
14 hours ago
$begingroup$
The decision version of your problem is: Given a graph and a number $ell$, is there a path whose length is shorter than $ell$? This is clearly in NP.
$endgroup$
– Yuval Filmus
6 hours ago
$begingroup$
The decision version of your problem is: Given a graph and a number $ell$, is there a path whose length is shorter than $ell$? This is clearly in NP.
$endgroup$
– Yuval Filmus
6 hours ago
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Copied from my answer on cstheory.stackexchange.com:
Paths with no repeated vertices are called simple-paths, so you are looking for the shortest simple-path in a graph with negative-cycles.
This can be reduced from the longest-path problem. If there were a fast solver for your problem, then given a graph with only positive edge-weights, negating all the edge-weights and running your solver would give the longest path in the original graph.
Thus your problem is NP-Hard.
answered 5 hours ago
BlueRaja - Danny PflughoeftBlueRaja - Danny Pflughoeft
830613
$endgroup$
$begingroup$
Thanks for the answer. While I was looking for a conversion from SAT (as, based on Cook's theorem, it's what I know to be NPC), connecting the dots led me to "Hamiltonian path to longest path" en.wikipedia.org/wiki/Longest_path_problem#NP-hardness and then "3SAT to Hamiltonian path" geeksforgeeks.org/proof-hamiltonian-path-np-complete
$endgroup$
– Tin Man
2 hours ago
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%2f110147%2fproof-that-shortest-path-with-negative-cycles-is-np-hard%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Copied from my answer on cstheory.stackexchange.com:
Paths with no repeated vertices are called simple-paths, so you are looking for the shortest simple-path in a graph with negative-cycles.
This can be reduced from the longest-path problem. If there were a fast solver for your problem, then given a graph with only positive edge-weights, negating all the edge-weights and running your solver would give the longest path in the original graph.
Thus your problem is NP-Hard.
answered 5 hours ago
BlueRaja - Danny PflughoeftBlueRaja - Danny Pflughoeft
830613
$endgroup$
$begingroup$
Thanks for the answer. While I was looking for a conversion from SAT (as, based on Cook's theorem, it's what I know to be NPC), connecting the dots led me to "Hamiltonian path to longest path" en.wikipedia.org/wiki/Longest_path_problem#NP-hardness and then "3SAT to Hamiltonian path" geeksforgeeks.org/proof-hamiltonian-path-np-complete
$endgroup$
– Tin Man
2 hours ago
add a comment |
$begingroup$
Copied from my answer on cstheory.stackexchange.com:
Paths with no repeated vertices are called simple-paths, so you are looking for the shortest simple-path in a graph with negative-cycles.
This can be reduced from the longest-path problem. If there were a fast solver for your problem, then given a graph with only positive edge-weights, negating all the edge-weights and running your solver would give the longest path in the original graph.
Thus your problem is NP-Hard.
answered 5 hours ago
BlueRaja - Danny PflughoeftBlueRaja - Danny Pflughoeft
830613
$endgroup$
$begingroup$
Thanks for the answer. While I was looking for a conversion from SAT (as, based on Cook's theorem, it's what I know to be NPC), connecting the dots led me to "Hamiltonian path to longest path" en.wikipedia.org/wiki/Longest_path_problem#NP-hardness and then "3SAT to Hamiltonian path" geeksforgeeks.org/proof-hamiltonian-path-np-complete
$endgroup$
– Tin Man
2 hours ago
add a comment |
$begingroup$
Copied from my answer on cstheory.stackexchange.com:
Paths with no repeated vertices are called simple-paths, so you are looking for the shortest simple-path in a graph with negative-cycles.
This can be reduced from the longest-path problem. If there were a fast solver for your problem, then given a graph with only positive edge-weights, negating all the edge-weights and running your solver would give the longest path in the original graph.
Thus your problem is NP-Hard.
answered 5 hours ago
BlueRaja - Danny PflughoeftBlueRaja - Danny Pflughoeft
830613
$endgroup$
Copied from my answer on cstheory.stackexchange.com:
Paths with no repeated vertices are called simple-paths, so you are looking for the shortest simple-path in a graph with negative-cycles.
This can be reduced from the longest-path problem. If there were a fast solver for your problem, then given a graph with only positive edge-weights, negating all the edge-weights and running your solver would give the longest path in the original graph.
Thus your problem is NP-Hard.
answered 5 hours ago
BlueRaja - Danny PflughoeftBlueRaja - Danny Pflughoeft
830613
answered 5 hours ago
BlueRaja - Danny PflughoeftBlueRaja - Danny Pflughoeft
830613
answered 5 hours ago
BlueRaja - Danny PflughoeftBlueRaja - Danny Pflughoeft
830613
answered 5 hours ago
BlueRaja - Danny PflughoeftBlueRaja - Danny Pflughoeft
830613
830613
$begingroup$
Thanks for the answer. While I was looking for a conversion from SAT (as, based on Cook's theorem, it's what I know to be NPC), connecting the dots led me to "Hamiltonian path to longest path" en.wikipedia.org/wiki/Longest_path_problem#NP-hardness and then "3SAT to Hamiltonian path" geeksforgeeks.org/proof-hamiltonian-path-np-complete
$endgroup$
– Tin Man
2 hours ago
add a comment |
$begingroup$
Thanks for the answer. While I was looking for a conversion from SAT (as, based on Cook's theorem, it's what I know to be NPC), connecting the dots led me to "Hamiltonian path to longest path" en.wikipedia.org/wiki/Longest_path_problem#NP-hardness and then "3SAT to Hamiltonian path" geeksforgeeks.org/proof-hamiltonian-path-np-complete
$endgroup$
– Tin Man
2 hours ago
$begingroup$
Thanks for the answer. While I was looking for a conversion from SAT (as, based on Cook's theorem, it's what I know to be NPC), connecting the dots led me to "Hamiltonian path to longest path" en.wikipedia.org/wiki/Longest_path_problem#NP-hardness and then "3SAT to Hamiltonian path" geeksforgeeks.org/proof-hamiltonian-path-np-complete
$endgroup$
– Tin Man
2 hours ago
$begingroup$
Thanks for the answer. While I was looking for a conversion from SAT (as, based on Cook's theorem, it's what I know to be NPC), connecting the dots led me to "Hamiltonian path to longest path" en.wikipedia.org/wiki/Longest_path_problem#NP-hardness and then "3SAT to Hamiltonian path" geeksforgeeks.org/proof-hamiltonian-path-np-complete
$endgroup$
– Tin Man
2 hours ago
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%2f110147%2fproof-that-shortest-path-with-negative-cycles-is-np-hard%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
2
$begingroup$
Do you have to reduce from SAT? A simple reduction is from Hamiltonian path.
$endgroup$
– Juho
14 hours ago
$begingroup$
The decision version of your problem is: Given a graph and a number $ell$, is there a path whose length is shorter than $ell$? This is clearly in NP.
$endgroup$
– Yuval Filmus
6 hours ago