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
line break after the word "proof" in proof environment
What is the technical explanation of the note "A♭" in a F7 chord in the key of C?
What are the benefits to casting without the need for somatic components?
Why aren't globular clusters disk shaped
Getting fresh water in the middle of hypersaline lake in the Bronze Age
What do mathematicians mean when they say some conjecture can’t be proven using the current technology?
Too many spies!
Is there a way to handmake alphabet pasta?
In special relativity is mass just a measure of all other energy than kinetic?
What are the arguments for California’s nonpartisan blanket primaries?
Why do candidates not quit if they no longer have a realistic chance to win in the 2020 US presidents election
If I stood next to a piece of metal heated to a million degrees, but in a perfect vacuum, would I feel hot?
What impact would a dragon the size of Asia have on the environment?
What's the phrasal verb for carbonated drinks exploding out of the can after being shaken?
What are "full piece" and "half piece" in chess?
What made Windows ME so crash-prone?
Project Euler, problem # 9, Pythagorean triplet
Is dividends exclusively a part of earnings?
I won USD 50K! Now what should I do with it?
Why hasn't the U.S. government paid war reparations to any country it attacked?
I do not have power to all my breakers
Doing research in academia and not liking competition
Applying for a USA B1/B2 Visa for an alien resident in Germany
Why does the Earth have a z-component at the start of the J2000 epoch?
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 8 hours ago
yusixieyusixie
1217 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 8 hours ago
yusixieyusixie
1217 bronze badges
$endgroup$
$begingroup$
Somewhat related: xkcd.com/230
$endgroup$
– Asaf Karagila♦
26 mins ago
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 8 hours ago
yusixieyusixie
1217 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 8 hours ago
yusixieyusixie
1217 bronze badges
asked 8 hours ago
yusixieyusixie
1217 bronze badges
asked 8 hours ago
yusixieyusixie
1217 bronze badges
asked 8 hours ago
yusixieyusixie
1217 bronze badges
asked 8 hours ago
yusixieyusixie
1217 bronze badges
1217 bronze badges
$begingroup$
Somewhat related: xkcd.com/230
$endgroup$
– Asaf Karagila♦
26 mins ago
add a comment |
$begingroup$
Somewhat related: xkcd.com/230
$endgroup$
– Asaf Karagila♦
26 mins ago
$begingroup$
Somewhat related: xkcd.com/230
$endgroup$
– Asaf Karagila♦
26 mins ago
$begingroup$
Somewhat related: xkcd.com/230
$endgroup$
– Asaf Karagila♦
26 mins ago
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 8 hours ago
Henning MakholmHenning Makholm
252k17 gold badges332 silver badges574 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 8 hours ago
Henning MakholmHenning Makholm
252k17 gold badges332 silver badges574 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 8 hours ago
Henning MakholmHenning Makholm
252k17 gold badges332 silver badges574 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 8 hours ago
Henning MakholmHenning Makholm
252k17 gold badges332 silver badges574 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 8 hours ago
Henning MakholmHenning Makholm
252k17 gold badges332 silver badges574 bronze badges
answered 8 hours ago
Henning MakholmHenning Makholm
252k17 gold badges332 silver badges574 bronze badges
answered 8 hours ago
Henning MakholmHenning Makholm
252k17 gold badges332 silver badges574 bronze badges
answered 8 hours ago
Henning MakholmHenning Makholm
252k17 gold badges332 silver badges574 bronze badges
252k17 gold badges332 silver badges574 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
$begingroup$
Somewhat related: xkcd.com/230
$endgroup$
– Asaf Karagila♦
26 mins ago