# Algorithm to find if exists a k-length acyclic path with negative weight on an weighted undirected graph

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)

• What's an "acyclic path"? What's the input to the problem? The graph and $k$? – 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$.