Lower bounds on the complexity of mixed-integer programs for stable set and knapsack

Standard mixed-integer programming formulations for the stable set problem on n-node graphs require n integer variables. We prove that this is almost optimal: We give a family of n-node graphs for which every polynomial-size MIP formulation requires Ω(n/log2n) integer variables. By a polyhedral reduction we obtain an analogous result for n-item knapsack problems. In both cases, this improves the previously known bounds of Ω(n/logn) by Cevallos et al. (in Proceedings of the twenty-ninth annual ACM-SIAM symposium on discrete algorithms (SODA), SIAM, 2018). To this end, we show that there exists a family of n-node graphs whose stable set polytopes satisfy the following: any (1+εn)-approximate extended formulation for these polytopes, for some constant ε>0, has size 2Ω(n/logn). Our proof extends and simplifies the information-theoretic methods due to Göös et al. (SIAM J Comput 47(1):241–269, 2018) who showed the same result for the case of exact extended formulations (i.e. ε=0).