A first efficient algorithm for enumerating all the extreme points of a bisubmodular polyhedron

Abstract

Efficiently enumerating all the extreme points of a polytope identified by a system of linear inequalities is a well-known challenge issue.We consider a special case and present an algorithm that enumerates all the extreme points of a bisubmodular polyhedron in $\mathcal{O}(n^4|V|)$ time and $\mathcal{O}(n^2)$ space complexity, where $n$ is the dimension of underlying space and $V$ is the set of outputs. We use the reverse search and signed poset linked to extreme points to avoid the redundant search. Our algorithm is a generalization of enumerating all the extreme points of a base polyhedron which comprises some combinatorial enumeration problems.

arXiv comment2 pages, 3 figures