2016/11/20 by Benchetrit, Yohann, Fiorini, Samuel, Huynh, Tony +1 · 1 citation
#Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC)
paper · doi:10.48550/arxiv.1611.06593
Let S ⊆ \0,1\n and R be any polytope contained in [0,1]n with R ∩ \0,1\n = S. We prove that R has bounded Chvátal-Gomory rank (CG-rank) provided that S has bounded notch and bounded gap, where the notch is the minimum integer p such that all p-dimensional faces of the 0/1-cube have a nonempty intersection with S, and the gap is a measure of the size of the facet coefficients of conv(S). Let H[S] denote the subgraph of the n-cube induced by the vertices not in S. We prove that if H[S] does not contain a subdivision of a large complete graph, then both the notch and the gap are bounded. By our main result, this implies that the CG-rank of R is bounded as a function of the treewidth of H[S]. We also prove that if S has notch 3, then the CG-rank of R is always bounded. Both results generalize a recent theorem of Cornuéjols and Lee, who proved that the CG-rank is bounded by a constant if the treewidth of H[S] is at most 2.