Consider the decision problem:
"Given a complete weighted graph $G=(V,E)$, an integer $k\in\mathbb N$ and two nodes $s,t\in V$ decide if $G$ has a path of at least weight $k$"
I had to show whether it was in P, NP or coNP.I had no problems figuring out that it's in NP and isn't in coNP but i got a curiosity on proving that it's not in P. Considering its similarity with TSP i thought that showing a reduction from TSP was the fastest way to prove its NP-completeness:
- get an instance of TSP with a graph $G=(V,E)$
- make a copy of the graph $G'=(V',E')$ for the instance of the problem
- assign weight $k$ to all the edges of the path of TSP on $G'$
- assign weight $0$ to all other edges so that only if TSP has a solution the problem has one
Could the reduction still be made if the edges couldn't have weight 0? i might be missing something but i'm fairly new to the subject
