Generating all vertices of a polyhedron is hard (Q5920505): Difference between revisions

Consider a directed edge-weighted graph \(G\) where the arcs are weighted by real values. A cycle is negative if the sum of its edge weights is negative. The number of negative cycles may be exponential in the size of the input, i.e. the size of \(G\) and the weights. The main result says that enumerating all negative cycles is NP-hard, even if the edge weights consist of only two different values. The same result holds for the undirected case. As a consequence, enumerating all minimal infeasible subsystems of a system of linear inequalities is NP-hard. This is even true for linear systems involving at most two variables in each inequality. For generating maximal feasible subsystems the complexity is open. Enumerating all vertices of a rational polyhedron, given as the intersection of finitely many half-spaces, is NP-hard. For bounded polyhedra the complexity remains open.