Is this variant of Exact Path Length Problem easy or NP Complete

I was reading about the longest path problem and it is NP Complete.

What about the problem where we need to find a path of some exact length $K$. All edges are directed. We are also allowed to repeat edges and vertices and all weights are positive.

The reason is where ever I look they in the definition emphasize:

• Simple paths or

• Weights are both positive and negative.

https://en.wikipedia.org/wiki/Longest_path_problem
https://www.sciencedirect.com/science/article/abs/pii/S0196677401912015

So I wonder if those 2 conditions are necessary for NP Completeness.

The reason for simple paths for the longest path problem is simple (pun not intended):

• either there is a cycle of positive weight, and therefore the longest path is not really defined as it could have an infinite weight;

• or all cycles have non-positive weight, and the longest path is a simple path.

As for weight values, if you can find a longest path in a graph with positive and negative weights, you can also do it in a graph with only positive weights (because no negative weights is only a particular case).

As for the exact weight path problem, it is also $\mathsf{NP}$-hard. There is a possible reduction from the Hamiltonian path problem.

Given a digraph $G = (V, E)$ with $V=\{v_1, …, v_n\}$, consider $G' = (V', E', f)$ such that:

• $V' = \{v_{i,k}\mid i,k \in \{1, …, n\}\} \cup \{s, t\}$;

• $E' = \{(v_{i,k}, v_{j,k+1})\mid k\in \{1, …, n-1\} \text{ and }(v_i, v_j)\in E\}\cup \{(s, v_{i,1})\mid i\in \{1, …, n\}\}\cup \{(v_{i,n}, t)\mid i\in \{1, …, n\}\}$;

• for $e = (u, v)\in E'$, $f(e) = n^i$ if $v=v_{i,k}$ and $f(e) = 1$ if $v = t$.

Then I claim (if I am not mistaken) that there exists a Hamiltonian path in $G$ if and only if there exists a path of weight $W=\sum\limits_{i=0}^n n^i$ in $G'$. The idea is that given that the second index is incremented in each edge, a path in $G'$ can only contain at most $n+1$ edges (from $s$ to $t$). Also, it is not possible to cross two edges of the same weight twice (otherwise it would not be possible to get the total weight $W$).

StackExchange Computer Science Q#156909, answer score: 5