|Generating all vertices of a polyhedron is hard.
(Rutgers Center for Operations Reseach,
The State University of New Jersey,
Adjunct Professor and@Researcher )
^CgFGenerating all vertices of a polyhedron is hard.
We show that generating all negative directed cycles of a directed graph is a hard generating problem. More precisely, given a digraph and a collection of its negative dicycles, it is NP-hard to decide whether this collection is complete.
As a corollary we solve in negative two well-known generating problems from linear programming:
(i) Given an infeasible system of linear inequalities, generating all its minimal infeasible subsystems(so-called Helly subsystems) is hard.
Yet, for 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