  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 negative cost cycle with at least $k$ edges, and the
fixed-point \emph{$k$-}length negative cost cycle \emph{trail (FP$k$LNCCT)}
problem is to determine whether there exists a negative trail enrouting a given
vertex (as the fixed point) and containing only cycles with at least $k$ edges.
The $k$\emph{LNCC} problem first emerged in deadlock avoidance in synchronized
streaming computing network \cite{spaa10}, generalizing two famous problems:
negative cycle detection and the $k$-cycle problem. As a warmup by-production,
the paper first shows that \emph{FP$k$LNCCT is }${\cal NP}$-complete in
multigraph\emph{ }even for\emph{ $k=3$} by reducing from the \emph{3SAT}
problem. Then as the main result, we prove the ${\cal NP}$-completeness of
$k$\emph{LNCC} by giving a sophisticated reduction from the 3 Occurrence
3-Satisfiability (\emph{3O3SAT}) problem, a known ${\cal NP}$-complete special
case of 3SAT in which a variable occurs at most three times. The complexity
result is interesting, since polynomial time algorithms are known for both
$2$\emph{LNCC} (essentially no restriction on the value of $k$) and the
$k$-cycle problem of fixed $k$. This paper closes the open problem proposed by
Li et al. in \cite{spaa10} whether $k$\emph{LNCC} admits polynomial-time
algorithms.
