It is a notorious open question whether integer programs (IPs) with an integer coefficient matrix M whose subdeterminants are all bounded by a constant Δ in absolute value can be solved in polynomial time. We answer this question in the affirmative if we further require that, by removing a constant number of rows and columns from M, one obtains a submatrix A that is the transpose of a network matrix.

We study the feedback vertex set problem in tournaments from the polyhedral point of view, and in particular we show that performing just one round of the Sherali–Adams hierarchy gives a relaxation with integrality gap 7/3. This allows us to derive a 7/3-approximation algorithm for the feedback vertex set problem in tournaments that matches the best deterministic approximation guarantee due to Mnich, Williams, and Végh, and is a simplification and runtime improvement of their approach.

$2$-level polytopes naturally appear in several areas of pure and applied mathematics, including combinatorial optimization, polyhedral combinatorics, communication complexity, and statistics. In this paper, we present a study of some $2$-level polytopes arising in combinatorial settings. Our first contribution is proving that $f_0(P)f_{d-1}(P)\leq d2^{d+1}$ for a large collection of families of such polytopes $P$. Here $f_0(P)$ (resp., $f_{d-1}(P)$) is the number of vertices (resp., facets) of $P$, and $d$ is its dimension. Whether this holds for all 2-level polytopes was asked in [A. Bohn, Y. Faenza, S. Fiorini, V. Fisikopoulos, M. Macchia, and K. Pashkovich, in Algorithms--ESA 2015, Springer, Berlin, 2015, pp. 191--202], and experimental results from [S. Fiorini, V. Fisikopoulos, and M. Macchia, in Combinatorial Optimization, Springer, Cham, 2016, pp. 285--296] showed it true for $d\leq 7$. The key to most of our proofs is a deeper understanding of the relations among those polytopes and their underlying combinatorial structure. This leads to a number of results that we believe to be of independent interest: a trade-off formula for the number of cliques and stable sets in a graph, a description of stable matching polytopes as affine projections of certain order polytopes, and a linear-size description of the base polytope of matroids that are 2-level in terms of cuts of an associated tree.