Generating All Vertices of a Polyhedron Is Hard

2008/03/01 by Leonid Khachiyan, Endre Boros, Konrad Borys +2 · 3 citations
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Optimization and Packing Problems #Polyhedron #Combinatorics #Mathematics #Corollary #Enumeration #Bounded function #Time complexity #Directed graph #Undirected graph #Discrete mathematics #Linear inequality #Strongly connected component #Graph #Inequality

paper · pdf · doi:10.1007/s00454-008-9050-5

openalex publication_date 2008/03/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/23

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

Citations

• Identifying the Minimal Transversals of a Hypergraph and Related Problems
• A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
• Algorithm 97: Shortest path
• The complexity of theorem-proving procedures
• A Theorem on Boolean Matrices
• The Complexity of Enumeration and Reliability Problems

Cited by

• Weighted digraphs and tropical cones
• Computing the bounded subcomplex of an unbounded polyhedron
• Endre Boros [wikipedia]

Related

• Characterization of the Vertices and Extreme Directions of the Negative Cycles Polyhedron and Hardness of Generating Vertices of 0/1-Polyhedra
• Polynomial time vertex enumeration of convex polytopes of bounded branch-width
• On the Complexity of Detecting Constrained Negative Cost Cycles
• Hard Problems That Quickly Become Very Easy
• Solving Totally Unimodular LPs with the Shadow Vertex Algorithm