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



Your Answer

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

Browse other questions tagged or ask your own question.