2013/09/10 by Gustavo Angulo, Gustavo Barriga Angulo, Shabbir Ahmed +6
Computer Science · Engineering · Mathematics · #90C05 #90C57 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Optimization and Control (math.OC) #graph theory and CDMA systems #math.CO #math.OC #msc:90C05 #msc:90C57
paper · pdf · doi:10.48550/arxiv.1309.2545
15 pages
openalex publication_date 2013/09/10 · arxiv created 2014/03/01 · arxiv updated 2014/03/04 · openalex created_date 2022/10/01 · openalex updated_date 2026/07/28
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.