Generating vertices of polyhedra and related monotone generation problems

Khaled Elbassioni, Max Planck Institute, Saarbruecken, Germany

The well-known vertex enumeration problem calls for generating all the vertices of a polyhedron, given by its description as a system of linear inequalities. We show that the problem is NP-hard for unbounded polyhedra, and also argue that the method used to enumerate the vertices of 0/1-polytopes is unlikely to work for 0/1-polyhedra. We then consider some monotone formulations for vertex enumeration and some other related problems, and discuss their connection to the hypergraph transversal problem.

back to EIDMA Seminar Combinatorial Theory announcements