Polyhedral Bounds for Forbidden-Vertices Sets and No-Good Cut Relaxations

We study the convex hull obtained after deleting prescribed vertices from the binary cube. The analysis separates three regimes according to the number of deleted vertices. When this number is fixed, both the original-space facet count and the linear extension complexity remain linear in the ambient dimension, up to constants depending only on the number of deleted vertices. When the deleted set grows, this behavior disappears: polynomially many forbidden vertices can force superpolynomially many facets and superlinear extension complexity, while unrestricted deletions can reach superexponentially many facets and exponential extension complexity. We also compare the no-good relaxation with known valid inequalities for structured forbidden sets, deriving exact violation bounds and a worst-case gap after adding all inequalities considered.

Article

Download

View PDF