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$ Commented 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$ Commented 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$ Commented Jul 18, 2019 at 7:17

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.