Does knowing a graph has a Hamiltonian Cycle make it easier to find the cycle?Existance of Hamiltonian cycle in the connected graph.How to prove that no hamiltonian cycle exists in the graphAny graph from the Petersen graph has a hamiltonian cycle if one edge is added(Graph Theory) Prove that $H_n$ has a Hamiltonian cycle for $n$ ≥ 2.The existance of a cycle of length $n/2$ in a simple graph is NP-CompleteHow to prove that a graph has a Hamiltonian cycle?$G$ has a Hamiltonian path iff $G+v$ has a Hamiltonian cycleHamiltonian Cycle with n vertex graphProof that if graph has $frac(n-1)(n-2)2 + 2$ edged then contains hamiltonian cycleEvery cubic 3-connected Hamiltonain graph has three Hamiltonian cycles with special property
Explanation for a joke about a three-legged dog that walks into a bar
USA: Can a witness take the 5th to avoid perjury?
Why did computer video outputs go from digital to analog, then back to digital?
Terence Tao - type books in other fields?
Where is this photo of a group of hikers taken? Is it really in the Ural?
How can I receive packages while in France?
How did C64 games handle music during gameplay?
"I you already know": is this proper English?
Where to place an artificial gland in the human body?
Should I leave my PhD after 3 years with a Masters?
How to write a sincerely religious protagonist without preaching or affirming or judging their worldview?
How do I run a game when my PCs have different approaches to combat?
What is a reasonable time for modern human society to adapt to dungeons?
How important is a good quality camera for good photography?
Is the statement 'Gods love the mysterious' also found in the Vedic Samhitas?
What exactly makes a General Products hull nearly indestructible?
What was the rationale behind 36 bit computer architectures?
Company requiring me to let them review research from before I was hired
Determine if a triangle is equilateral, isosceles, or scalene
Monty Hall Problem with a Fallible Monty
Sitecore Powershell extensions module compatibility with Sitecore 9.2
How do campaign rallies gain candidates votes?
Should I describe a character deeply before killing it?
Would it be a good idea to memorize relative interval positions on guitar?
Does knowing a graph has a Hamiltonian Cycle make it easier to find the cycle?
Existance of Hamiltonian cycle in the connected graph.How to prove that no hamiltonian cycle exists in the graphAny graph from the Petersen graph has a hamiltonian cycle if one edge is added(Graph Theory) Prove that $H_n$ has a Hamiltonian cycle for $n$ ≥ 2.The existance of a cycle of length $n/2$ in a simple graph is NP-CompleteHow to prove that a graph has a Hamiltonian cycle?$G$ has a Hamiltonian path iff $G+v$ has a Hamiltonian cycleHamiltonian Cycle with n vertex graphProof that if graph has $frac(n-1)(n-2)2 + 2$ edged then contains hamiltonian cycleEvery cubic 3-connected Hamiltonain graph has three Hamiltonian cycles with special property
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty margin-bottom:0;
$begingroup$
Given a simple and connected graph $G=(V, E)$. I know it's NP-Complete to determine if $G$ has a Hamiltonian Cycle (HC). But if we know $G$ indeed contains an HC, can we find the cycle in poly-time?
combinatorics graph-theory hamiltonian-path
asked Jul 15 at 14:44
yusixieyusixie
1317 bronze badges
$endgroup$
add a comment |
$begingroup$
Given a simple and connected graph $G=(V, E)$. I know it's NP-Complete to determine if $G$ has a Hamiltonian Cycle (HC). But if we know $G$ indeed contains an HC, can we find the cycle in poly-time?
combinatorics graph-theory hamiltonian-path
asked Jul 15 at 14:44
yusixieyusixie
1317 bronze badges
$endgroup$
1
$begingroup$
Somewhat related: xkcd.com/230
$endgroup$
– Asaf Karagila♦
Jul 15 at 23:09
add a comment |
$begingroup$
Given a simple and connected graph $G=(V, E)$. I know it's NP-Complete to determine if $G$ has a Hamiltonian Cycle (HC). But if we know $G$ indeed contains an HC, can we find the cycle in poly-time?
combinatorics graph-theory hamiltonian-path
asked Jul 15 at 14:44
yusixieyusixie
1317 bronze badges
$endgroup$
Given a simple and connected graph $G=(V, E)$. I know it's NP-Complete to determine if $G$ has a Hamiltonian Cycle (HC). But if we know $G$ indeed contains an HC, can we find the cycle in poly-time?
combinatorics graph-theory hamiltonian-path
combinatorics graph-theory hamiltonian-path
asked Jul 15 at 14:44
yusixieyusixie
1317 bronze badges
asked Jul 15 at 14:44
yusixieyusixie
1317 bronze badges
asked Jul 15 at 14:44
yusixieyusixie
1317 bronze badges
asked Jul 15 at 14:44
yusixieyusixie
1317 bronze badges
asked Jul 15 at 14:44
yusixieyusixie
1317 bronze badges
1317 bronze badges
1
$begingroup$
Somewhat related: xkcd.com/230
$endgroup$
– Asaf Karagila♦
Jul 15 at 23:09
add a comment |
1
$begingroup$
Somewhat related: xkcd.com/230
$endgroup$
– Asaf Karagila♦
Jul 15 at 23:09
1
1
$begingroup$
Somewhat related: xkcd.com/230
$endgroup$
– Asaf Karagila♦
Jul 15 at 23:09
$begingroup$
Somewhat related: xkcd.com/230
$endgroup$
– Asaf Karagila♦
Jul 15 at 23:09
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
No (or rather: no, unless P=NP).
If it were so, then there would be a concrete polynomial $p$ that bounded the running time of such an algorithm. Therefore you would be able to detect whether a graph has a Hamiltonian cycle by lying to the algorithm: Claim that the graph has a Hamiltonian cycle, run it for $p(n)$ steps, and then check whether by then it has printed a correct cycle or not.
answered Jul 15 at 14:49
Henning MakholmHenning Makholm
253k17 gold badges334 silver badges577 bronze badges
$endgroup$
add a comment |
Your Answer
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
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: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
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
,
noCode: 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%2fmath.stackexchange.com%2fquestions%2f3293840%2fdoes-knowing-a-graph-has-a-hamiltonian-cycle-make-it-easier-to-find-the-cycle%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$
No (or rather: no, unless P=NP).
If it were so, then there would be a concrete polynomial $p$ that bounded the running time of such an algorithm. Therefore you would be able to detect whether a graph has a Hamiltonian cycle by lying to the algorithm: Claim that the graph has a Hamiltonian cycle, run it for $p(n)$ steps, and then check whether by then it has printed a correct cycle or not.
answered Jul 15 at 14:49
Henning MakholmHenning Makholm
253k17 gold badges334 silver badges577 bronze badges
$endgroup$
add a comment |
$begingroup$
No (or rather: no, unless P=NP).
If it were so, then there would be a concrete polynomial $p$ that bounded the running time of such an algorithm. Therefore you would be able to detect whether a graph has a Hamiltonian cycle by lying to the algorithm: Claim that the graph has a Hamiltonian cycle, run it for $p(n)$ steps, and then check whether by then it has printed a correct cycle or not.
answered Jul 15 at 14:49
Henning MakholmHenning Makholm
253k17 gold badges334 silver badges577 bronze badges
$endgroup$
add a comment |
$begingroup$
No (or rather: no, unless P=NP).
If it were so, then there would be a concrete polynomial $p$ that bounded the running time of such an algorithm. Therefore you would be able to detect whether a graph has a Hamiltonian cycle by lying to the algorithm: Claim that the graph has a Hamiltonian cycle, run it for $p(n)$ steps, and then check whether by then it has printed a correct cycle or not.
answered Jul 15 at 14:49
Henning MakholmHenning Makholm
253k17 gold badges334 silver badges577 bronze badges
$endgroup$
No (or rather: no, unless P=NP).
If it were so, then there would be a concrete polynomial $p$ that bounded the running time of such an algorithm. Therefore you would be able to detect whether a graph has a Hamiltonian cycle by lying to the algorithm: Claim that the graph has a Hamiltonian cycle, run it for $p(n)$ steps, and then check whether by then it has printed a correct cycle or not.
answered Jul 15 at 14:49
Henning MakholmHenning Makholm
253k17 gold badges334 silver badges577 bronze badges
answered Jul 15 at 14:49
Henning MakholmHenning Makholm
253k17 gold badges334 silver badges577 bronze badges
answered Jul 15 at 14:49
Henning MakholmHenning Makholm
253k17 gold badges334 silver badges577 bronze badges
answered Jul 15 at 14:49
Henning MakholmHenning Makholm
253k17 gold badges334 silver badges577 bronze badges
253k17 gold badges334 silver badges577 bronze badges
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics 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%2fmath.stackexchange.com%2fquestions%2f3293840%2fdoes-knowing-a-graph-has-a-hamiltonian-cycle-make-it-easier-to-find-the-cycle%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
1
$begingroup$
Somewhat related: xkcd.com/230
$endgroup$
– Asaf Karagila♦
Jul 15 at 23:09