Proof that shortest path with negative cycles is NP hard
Do the English have an ancient (obsolete) verb for the action of the book opening?
Is it possible to (7 day) schedule sleep time of a hard drive?
Notation of last measure of a song with a pickup measure
When writing an error prompt, should we end the sentence with a exclamation mark or a dot?
Company did not petition for visa in a timely manner. Is asking me to work from overseas, but wants me to take a paycut
Can an Eldritch Knight use Action Surge and thus Arcane Charge even when surprised?
Trapping Rain Water
How many pairs of subsets can be formed?
Select items in a list that contain criteria #2
Average spam confidence
Why don’t airliners have temporary liveries?
siunitx error: Invalid numerical input
What is the purpose of building foundations?
Deformation of rectangular plot
Where does this pattern of naming products come from?
Does an ice chest packed full of frozen food need ice?
Is it recommended against to open-source the code of a webapp?
Subtables with equal width?
Cause of continuous spectral lines
Traffic law UK, pedestrians
Why only the fundamental frequency component is said to give useful power?
How is it possible that Gollum speaks Westron?
4*4*4 Rubiks cube Top Layer Issue
Turing patterns
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
7 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
7 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
7 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
7 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
7 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 6 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 6 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 6 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 6 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 6 hours ago
BlueRaja - Danny PflughoeftBlueRaja - Danny Pflughoeft
830613
answered 6 hours ago
BlueRaja - Danny PflughoeftBlueRaja - Danny Pflughoeft
830613
answered 6 hours ago
BlueRaja - Danny PflughoeftBlueRaja - Danny Pflughoeft
830613
answered 6 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
7 hours ago