We show that generating all negative cycles of a weighted graph is a
hard enumeration problem, in both the directed and undirected cases.
More precisely, given a family of (directed) negative cycles, it is
NP-complete problem to decide whether this family can be extended or
there are no other negative (directed) cycles in the graph, implying
that (directed) negative cycles cannot be generated in polynomial
output time, unless P=NP.

As a corollary, we solve in the negative two well-known generating
problems from linear programming: (i) Given an (infeasible) system
of linear inequalities, generating all minimal infeasible subsystems
is hard. Yet, for generating maximal feasible subsystems the
complexity remains open. (ii) Given a (feasible) system of linear
inequalities, generating all vertices of the corresponding
polyhedron is hard. Yet, in case of bounded polyhedra the complexity
remains open