TY - JOUR

T1 - Generating all vertices of a polyhedron is hard

AU - Khachiyan, Leonid

AU - Boros, Endre

AU - Borys, Konrad

AU - Elbassioni, Khaled

AU - Gurvich, Vladimir

N1 - Funding Information:
This research was partially supported by the National Science Foundation (Grant IIS-0118635), and by DIMACS, the National Science Foundation’s Center for Discrete Mathematics and Theoretical Computer Science. An extended abstract of this paper appears in the Proceedings of the ACM–SIAM Symposium on Discrete Algorithms, Miami, Florida, January 22–24, 2006.

PY - 2008/3

Y1 - 2008/3

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=40349114631&partnerID=8YFLogxK

U2 - 10.1007/s00454-008-9050-5

DO - 10.1007/s00454-008-9050-5

M3 - Article

AN - SCOPUS:40349114631

SN - 0179-5376

VL - 39

SP - 174

EP - 190

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

IS - 1-3

ER -