0
$\begingroup$

I have a similar question as this post:Given a complete, weighted and undirected graph $G$, complexity of finding a path with a specific cost

My question: Given a weighted and directed graph $G$, it might contain negative cycles, is there a simple path(no repeated vertices) from $s$ to $t$ with total weight at most $T$?

We want to prove this question is NP-Complete, as I mentioned this is very similar to the post one, the only differences are my question mentioned negative cycles and the total weight is at most $T$ instead of exactly $T$. As the post suggested, we can reduce subset sum to our problem, but does it equivalent to asking the subset sum question sum to at most $T$ instead of sum to exactly T? Additionally, the reduction seems ignoring the property of negative cycles, but it still works somehow. Anyways, I'm really new to this field, like doing reduction and proving problems are NP-Complete. Any suggestion would be really helpful.

$\endgroup$
0
$\begingroup$

Consider all weights are -1. Now asking if there is a simple path with weight at most $-(n-1)$ is equivalent to asking if there is a Hamiltonian path. So your problem is NP-hard.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.