This question already has an answer here:

$\text{HAMPATH} = \{(G=(V,E),s',t')| \text{ G has a Hamilton path from s' to t' } \}$

$\text{LONG-PATH} = \{(G,s,t,k) | \text{G has a simple path p from s to t, length(p) $\geq$ k} \}$

I'm trying to prove a polynomial reduction, $\text{HAMPATH} \leq_p \text{LONG-PATH}$.

My thought was to take an instance of $\text{HAMPATH}$ and add exactly $k-|V|$ nodes and edges from $t'$ to $s'$, so i have an Hamilton path from $s=s'$ to $t'$, and a simple path(which is also an Hamilton path) from $t'$ to $t$.

I tried to prove that but i couldn't finish the proof and it seems that this is not good reduction.

any thoughts?


marked as duplicate by Raphael Jun 11 '14 at 13:51

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ How long is a Hamiltonian path? $\endgroup$ – Louis Jun 11 '14 at 13:38
  • 1
    $\begingroup$ Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$ – Raphael Jun 11 '14 at 13:50
  • $\begingroup$ @Louis, obviously |V|... $\endgroup$ – kitsuneFox Jun 11 '14 at 13:56
  • $\begingroup$ please help me.. $\endgroup$ – kitsuneFox Jun 13 '14 at 9:53