The Vertex Set of a 0/1-Polytope is Strongly
P-Enumerable (abstract)
In this paper, we discuss the computational complexity of the
following enumeration problem: Given a rational convex polyhedron
P defined by a system of linear inequalities, output each vertex of P.
It is still an open question whether there exists an algorithm for
listing all vertices in running time polynomial in the input size
and the output size. Informally speaking, a linear running time
in the output size leads to the notion of
P-enumerability introduced by
Valiant. The concept of strong P-enumerability
additionally requires an output
independent space complexity of the respective algorithm. We give
such an algorithm for polytopes, all of whose vertices are among the
vertices of a polytope combinatorially equivalent to the hypercube. As most
important special case, this
class of polytopes contains all 0/1-polytopes. Our implementation based on the
commercial LP solver CPLEX is superior to general
vertex enumeration algorithms. We give an example how simplifications of our algorithm
lead to efficient enumeration of combinatorial objects.
Keywords: Vertex enumeration, convex polyhedra, 0/1-polytopes,
strong P-enumerability, computational complexity
M.Luebbecke@tu-bs.de
Jul 8, 1997