hide
Free keywords:
-
Abstract:
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 negative (directed) cycles, it is an 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 the case of bounded polyhedra the complexity remains open
