Generating all vertices of a polyhedron is hard

DOI10.1007/S00454-008-9050-5zbMath1147.05040OpenAlexW2058094600WikidataQ59560590 ScholiaQ59560590MaRDI QIDQ5920505

Konrad Borys, Khaled M. Elbassioni, Endre Boros, Vladimir A. Gurvich, Leonid G. Khachiyan

Publication date: 16 April 2008

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00454-008-9050-5

zbMATH Keywords

enumerationNP-hardnegative cyclesdirected edge weighted graphinfeasible subsystems of system of linear inequalities

Mathematics Subject Classification ID

Linear programming (90C05) Enumeration in graph theory (05C30) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)

Related Items (35)

Weighted digraphs and tropical cones ⋮ Farkas Certificates and Minimal Witnesses for Probabilistic Reachability Constraints ⋮ On characterizing full dimensional weak facets in DEA with variable returns to scale technology ⋮ Computing convex hulls and counting integer points with \texttt{polymake} ⋮ On the approximation of unbounded convex sets by polyhedra ⋮ Revisited aspects of the local set in CHSH Bell scenario ⋮ Robust homecare service capacity planning ⋮ Enumerating minimal dominating sets in chordal bipartite graphs ⋮ Derivative-free optimization of a rapid-cycling synchrotron ⋮ A polynomial-time-delay and polynomial-space algorithm for enumeration problems in multi-criteria optimization ⋮ Gorenstein braid cones and crepant resolutions ⋮ Maximal admissible faces and asymptotic bounds for the normal surface solution space ⋮ Output-polynomial enumeration on graphs of bounded (local) linear MIM-width ⋮ The negative cycles polyhedron and hardness of checking some polyhedral properties ⋮ Computational tools for solving a marginal problem with applications in Bell non-locality and causal modeling ⋮ An incremental polynomial time algorithm to enumerate all minimal edge dominating sets ⋮ Scientific contributions of Leo Khachiyan (a short overview) ⋮ A new method for determining all maximal efficient faces in multiple objective linear programming ⋮ On the hardness of computing intersection, union and Minkowski sum of polytopes ⋮ Optimizing the double description method for normal surface enumeration ⋮ Self-duality of polytopes and its relations to vertex enumeration and graph isomorphism ⋮ Complexity and algorithms for computing Voronoi cells of lattices ⋮ Complexity of methods for approximating convex compact bodies by double description polytopes and complexity bounds for a hyperball ⋮ Static Contract Checking with Abstract Interpretation ⋮ Sum of Squares Certificates for Containment of $\mathcal{H}$-Polytopes in $\mathcal{V}$-Polytopes ⋮ A semidefinite programming approach for solving multiobjective linear programming ⋮ Efficient geometric operations on convex polyhedra, with an application to reachability analysis of hybrid systems ⋮ Enumerating Vertices of Covering Polyhedra with Totally Unimodular Constraint Matrices ⋮ A polyhedral model for enumeration and optimization over the set of circuits ⋮ Complexity of approximating the vertex centroid of a polyhedron ⋮ The regularized feasible directions method for nonconvex optimization ⋮ Enumerating Vertices of 0/1-Polyhedra associated with 0/1-Totally Unimodular Matrices ⋮ Exploiting Symmetries in Polyhedral Computations ⋮ Forbidden Vertices ⋮ Sampling and Statistical Physics via Symmetry

Uses Software

• Algorithm 97

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Random generation of combinatorial structures from a uniform distribution
• On generating all maximal independent sets
• A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
• The densest hemisphere problem
• The vertex set of a \(0/1\)-polytope is strongly \(\mathcal P\)-enumerable
• Primal-dual methods for vertex and facet enumeration
• Incremental convex hull algorithms are not output sensitive
• An optimal convex hull algorithm in any fixed dimension
• Efficient enumeration of the vertices of polyhedra associated with network LP's
• Some results concerning post-infeasibility analysis
• How good are convex hull algorithms?
• On the maximum feasible subsystem problem, IISs and IIS-hypergraphs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Reverse search for enumeration
• Analysis of backtrack algorithms for listing all vertices and all faces of a convex polyhedron.
• Maximum-Minimum Sätze über Graphen
• The Complexity of Vertex Enumeration Methods
• Finding the convex hull facet by facet
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• An Algorithm for Finding All Vertices of Convex Polyhedral Sets
• The Complexity of Enumeration and Reliability Problems
• Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
• Identifying Minimally Infeasible Subsystems of Inequalities
• Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning Trees
• An algorithm for determining all extreme points of a convex polytope
• IIS-Hypergraphs
• Identifying the Minimal Transversals of a Hypergraph and Related Problems
• An Algorithm for Convex Polytopes
• The complexity of theorem-proving procedures
• An Algorithm for Determining Irrelevant Constraints and all Vertices in Systems of Linear Inequalities
• Integer Programming and Combinatorial Optimization
• A Theorem on Boolean Matrices

This page was built for publication: Generating all vertices of a polyhedron is hard