  In this work, we introduce and study the forbidden-vertices problem. Given a
polytope P and a subset X of its vertices, we study the complexity of linear
optimization over the subset of vertices of P that are not contained in X. This
problem is closely related to finding the k-best basic solutions to a linear
problem. We show that the complexity of the problem changes significantly
depending on the encoding of both P and X. We provide additional tractability
results and extended formulations when P has binary vertices only. Some
applications and extensions to integral polytopes are discussed.
