On the Complexity of Detecting Constrained Negative Cost Cycles

Longkun Guo, Peng Li

Given a positive integer $k$ and a directed graph with a cost on each edge, the $k$-length negative cost cycle ($k$\emph{LNCC}) problem is to determine whether there exists a negat…