In 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.  In this paper we apply the concept of branch-decomposition to the vertex enumeration problem of polyhedra P = \{x : Sx = b, x \geq 0\}. Therefore , we introduce the concept of k-module and show how it relates to the separators of the linear matroid generated by the columns of S. This then translates structural properties of the matroidal branch-decomposition to the context of polyhedra. 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 S is bounded by a constant k.
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 \geq 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.
R
In
Over
A
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.
R
Sx
Ax
R
Therefore
For this purpose
R
S. This then translates structural properties of the matroidal branch-decomposition to the context of polyhedra.
A.
R
S
A