2014/04/22 by Reimers, Arne C., Stougie, Leen
#52B11 #52B40 #52C45 (Primary) #68Q25 (Secondary) #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Computational Geometry (cs.CG) #F.2.2 #FOS: Biological sciences #FOS: Computer and information sciences #FOS: Mathematics #I.1.2 #Molecular Networks (q-bio.MN)
paper · doi:10.48550/arxiv.1404.5584
Over the last years the vertex enumeration problem of polyhedra has seen a revival in the study of metabolic networks, which increased the demand for efficient vertex enumeration algorithms for high-dimensional polyhedra given by inequalities. It is a famous and long standing open question in polyhedral theory and computational geometry whether the vertices of a polytope (bounded polyhedron), described by a set of linear constraints, can be enumerated in total polynomial time. In this paper we apply the concept of branch-decomposition to the vertex enumeration problem of polyhedra P = \x : Ax = b, x ≥ 0\. For this purpose, we introduce the concept of k-module and show how it relates to the separators of the linear matroid generated by the columns of A. We then use this to present a total polynomial time algorithm for polytopes P for which the branch-width of the linear matroid generated by A is bounded by a constant k.