# Simple Hamiltonian cycle reduction

HAMPATH

• Input: An undirected graph $$G$$ and 2 nodes $$s, t$$

• Question: Does G contain a Hamiltonian path from $$s$$ to $$t$$?

HAMCYCLE

• Input: A undirected graph $$G$$ and a nodes $$s$$

• Question: Does $$G$$ contain a Hamiltonian cycle starting at $$s$$?

I wish to show HAMCYCLE is NP-hard. I'll show this by doing $$HAMPATH \leq_p HAMCYCLE$$ since HAMPATH is known to be NP-complete.

add edge from t to s

if theres a hampath then the reduction shows there a hamcycle

if theres a hamcycle then clearly theres a hampath

Above is my entire attempt. I was wondering if I could call on $$t$$ in my reduction since its not used as a input in HAMCYCLE?

## 1 Answer

Instead of cutting corners and jumping right in to a reduction, I believe you would profit from actually stepping back and clarifying the logical basis of your argument.

Given an instance $$(G, s, t)$$ of HAMPATH, your reduction produces an instance $$(G', s')$$ of HAMCYCLE, as you have described. To prove your reduction works, you need to show: $$(G, s, t) \in \textsf{HAMPATH} \iff (G', s') \in \textsf{HAMCYCLE}$$ for every instance $$(G, s, t)$$ of HAMPATH, where $$(G', s')$$ is uniquely determined as a function of $$(G, s, t)$$ (the function in case being your reduction).

To prove this equivalence, you first fix an arbitrary instance $$(G, s, t)$$ of HAMPATH (which may be a "yes" or a "no" instance). $$(G', s')$$ is then uniquely determined by $$(G, s, t)$$. Then, you either prove the two sides of the equivalence (as you have done) or show that, if $$(G, s, t)$$ is a "yes" instance, then $$(G', s')$$ is a "yes" instance and, if $$(G, s, t)$$ is a "no" instance, then $$(G', s')$$ is a "no" instance. Although usually the latter is preferred, either is fine; you can reference all of $$G$$, $$s$$, $$t$$, $$G'$$, and $$s'$$ in both cases since they are all fixed.

The problem with your argument is that you obtain a cycle $$(s, \dots, s)$$ and then (correctly) reason there is a node $$t'$$ right before $$s$$ which makes it a Hamiltonian cycle (and gives you a Hamiltonian path from $$s$$ to $$t'$$). However, because $$t$$ is fixed, there is no guarantee that $$t' = t$$. You still need to consider the case $$t' \neq t$$ and show this gives you a Hamiltonian path from $$s$$ to $$t$$ even if you delete the edge $$(t, s)$$ (since this yields $$G$$ from $$G'$$).

Unfortunately, you will not be able to. Consider, for instance, the case where $$G$$ is a cycle $$(s, t, v, s)$$. Then both $$G$$ and $$G'$$ obviously have a Hamiltonian cycle which starts and ends at $$s$$, but there is no Hamiltonian path from $$s$$ to $$t$$ in $$G$$; the only way to reach $$t$$ from $$s$$ (by a path) is the single edge $$(s, t)$$, which fails to visit the vertex $$v$$.

You will have to modify your reduction. Hint: Try to find a way of forcing $$G$$ to not have a Hamiltonian cycle in the first place (and note this implies $$t' = t$$ above).

• Thank you for your counter example I get why its wrong now. I've tried another reduction. – tom Jul 17 '19 at 23:42
• The reduction from G makes it so we get a path thats either $(s', t, t', s')$ or $(s', t, v, s')$ but one node will be excluded making it not a hamilton cycle. – tom Jul 18 '19 at 0:21
• @tom Sorry, this site isn't designed for back-and-forth interactive assistance. In fact, it is usually frowned upon to (significantly) modify or expand your question once a satisfactory answer has already been posted. If you have additional questions based on the answers you have received, then the way to go is asking a new question (and feel free to link to the former question when you do so). – dkaeae Jul 18 '19 at 7:17