2
$\begingroup$

I have a question, and also an answer which I assume, is correct, but would like to ask, if some of you could elaborate, and add validity to the provided claim or develop a discussion.

I did not find this question, nor the answer anywhere.

Question:

Is there any formal association or fundamental relationship, (as in some kind of theorem etc.) between Hamiltonian graphs and Eulerian graphs?

My answer:

No such thing exist. Simple proof is, that finding a Hamiltonian path in a graph is NP-hard problem, and finding Eulerian path is not a NP-hard problem. Or in other words: If this statement is indeed true, finding the Eulerian path should also be NP-hard problem, which we know is not.

$\endgroup$
  • $\begingroup$ "...finding the Eulerian path should also be NP-hard problem, which we know is not." implies $P \neq NP$ (which is not yet proved.) $\endgroup$ – Rebecca J. Stones Feb 8 '14 at 0:17
  • $\begingroup$ Finding Eulerian path is not NP-hard.That is completely true. $\endgroup$ – Satoshi Feb 8 '14 at 0:18
  • $\begingroup$ Do we agree EULERIAN PATH is in $P$? If $P=NP$, then $P=NP$-complete, and so every $P$ problem would be $NP$-hard. Therefore, if there exists a $P$ problem outside of $NP$-hard (as you're asserting), we must have $P \neq NP$. $\endgroup$ – Rebecca J. Stones Feb 8 '14 at 0:40
1
$\begingroup$

Your argument shows that you cannot interpret every Hamiltonian path problem as an Eulerian path problem.

However, your argument does not stop you from interpreting every Eulerian path problem as a Hamiltonian path problem which is both actually possible (by looking at the line graph) and pretty useless (it just shows that for an NP-hard problem there can be subclasses that are not NP-hard, but that is hardly surprising).

Whether this changes your answer depends on your definition of "formal association".

$\endgroup$
  • $\begingroup$ Thank you for elaborating.Maybe I've expressed myself a little bit awkward. I should have emphasized that we should focus on finding the answer and not so much on the interpretation of my solution itself. Thank you once again. $\endgroup$ – Satoshi Feb 8 '14 at 0:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.