A Proof for NP-completeness
Hint. Reduce Hamiltonian path to this problem. Use the rewards&nbsp;$r_i$ to say that you have to visit each city, use the costs&nbsp;$f_{i,j}$ to say that you can't use more than one edge per city and set the target $k$ to an appropriate value.