# A polynomial reduction from HAMPATH to LONG-PATH [duplicate]

$\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?

• How long is a Hamiltonian path? – Louis Jun 11 '14 at 13:38
• 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. – Raphael Jun 11 '14 at 13:50
• @Louis, obviously |V|... – kitsuneFox Jun 11 '14 at 13:56