Journal
DISCRETE & COMPUTATIONAL GEOMETRY
Volume 39, Issue 1-3, Pages 174-190Publisher
SPRINGER
DOI: 10.1007/s00454-008-9050-5
Keywords
-
Categories
Ask authors/readers for more resources
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. Equiva lently, the complexity of generating vertices and extreme rays of polyhedra remains open.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available