1
$\begingroup$

This is the same problem here but with one more condition that the sum of the distance cannot be a negative integer.

The full description of the problem is: Is it possible to find a simple path (no repeated vertices) between two vertices in a graph such that the sum of the weights of its constituent edges (the weight of an edge can be negative) is less than K, in which K is a positive number.

I have seen other reductions from the Hamilton Path problem, like

Those questions are different from the one I listed here. How to reduce the Hamilton path problem to this problem? Or is it possible to achieve this?

$\endgroup$
2
  • $\begingroup$ I'm confused. Please state the problem you want solved in a self-contained manner, in the question. Do you want to require that the sum of the weights be non-negative, or not? Such a condition doesn't appear in the second paragraph. $\endgroup$
    – D.W.
    Commented Apr 28 at 4:05
  • $\begingroup$ @D.W. Hi, yes I want to require that the sum of the weights be non-negative. In the 2nd paragraph, it is stated as the sum of the weights .... K is a positive number. $\endgroup$
    – Lebecca
    Commented Apr 30 at 16:18

1 Answer 1

3
$\begingroup$

There is an easy reduction from s-t-Hamilton path, to prove your problem is NP-hard:

Given a Graph (V, E) and two vertices s and t (the s-t-Hamilton path instance), construct an instance for your problem in the following way: Add a vertex s' and an edge (s', s), set the cost of this edge to n (where n = |V(G)|) and the cost of all other edges to -1 and K to 1.

Now there exists a simple s'-t path in your new instance with cost 1 iff there is a Hamilton s-t-path in the original instance.

As this is clearly a special case of a problem known to be in NP, your problem is therefore NP-complete.

$\endgroup$

Your Answer

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

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