DIMACS TR: 2005-21
Generating all vertices of a polyhedron is hard
Authors: Leonid Khachiyan, Endre Boros, Konrad Borys, Khaled Elbassioni and Vladimir Gurvich
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 (directed)
negative 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
keywords polytope, polyhedron, polytope-polyhedron problem, vertex, face, facet, enumeration
problem, vertex enumeration, facet enumeration, graph, cycle, negative cycle, linear
inequalities, feasible system
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2005/2005-21.pdf
DIMACS Home Page