1
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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).

$\endgroup$
3
  • $\begingroup$ Thank you for your counter example I get why its wrong now. I've tried another reduction. $\endgroup$
    – tom
    Jul 17, 2019 at 23:42
  • $\begingroup$ 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. $\endgroup$
    – tom
    Jul 18, 2019 at 0:21
  • 1
    $\begingroup$ @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). $\endgroup$
    – dkaeae
    Jul 18, 2019 at 7:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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