Consider the following problem: given an undirected graph with weighted edges (positive and negative) I would like to know if there is a k-length acyclic path with negative weight. Is there an algorithm for that with a good complexity? Maybe I can find the lighter k-length acyclic path and check if is negative, but it could be that this approach may have a bigger complexity. Let me know what do you think.

(Sorry for the lousy english)

  • 2
    $\begingroup$ What's an "acyclic path"? What's the input to the problem? The graph and $k$? $\endgroup$ – David Richerby Jun 1 '17 at 8:22

If $k$ is part of the input to the algorithm (as opposed to a constant chosen ahead of time), and if "acyclic path" means a path that does not visit any vertex more than once, then this problem is already at least as hard as Hamiltonian Path, which is NP-hard: to reduce the latter to this problem, just give every edge some negative weight (e.g., -1) and set $k=n−1$.


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.