Abstract
The extension complexity \(\mathsf {xc}(P)\) of a polytope P is the minimum number of facets of a polytope that affinely projects to P. Let G be a bipartite graph with n vertices, m edges, and no isolated vertices. Let \({{\mathrm{\mathsf {STAB}}}}(G)\) be the convex hull of the stable sets of G. It is easy to see that \(n \leqslant \mathsf {xc}({{\mathrm{\mathsf {STAB}}}}(G)) \leqslant n+m\). We improve both of these bounds. For the upper bound, we show that \(\mathsf {xc}({{\mathrm{\mathsf {STAB}}}}(G))\) is \(O(\frac{n^2}{\log n})\), which is an improvement when G has quadratically many edges. For the lower bound, we prove that \(\mathsf {xc}({{\mathrm{\mathsf {STAB}}}}(G))\) is \(\varOmega (n \log n)\) when G is the incidence graph of a finite projective plane. We also provide examples of 3-regular bipartite graphs G such that the edge vs stable set matrix of G has a fooling set of size |E(G)|.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Conforti, M., Cornuéjols, G., Zambelli, G.: Extended formulations in combinatorial optimization. Ann. Oper. Res. 204, 97–143 (2013)
Conforti, M., Cornuéjols, G., Zambelli, G.: Integer programming. Graduate Texts in Mathematics, vol. 271. Springer, Cham (2014)
Coxeter, H.S.M.: Projective Geometry, Revised reprint of the 2 edn. Springer, New York (1994)
Edmonds, J.: Paths, trees, and flowers. Canad. J. Math. 17, 449–467 (1965)
Edmonds, J.: Matroids and the greedy algorithm. Math. Program. 1, 127–136 (1971)
Fiorini, S., Kaibel, V., Pashkovich, K., Theis, D.O.: Combinatorial bounds on nonnegative rank and extended formulations. Discrete Math. 313(1), 67–83 (2013)
Fiorini, S., Massar, S., Pokutta, S., Tiwary, H.R., Wolf, R.D.: Exponential lower bounds for polytopes in combinatorial optimization. J. ACM 62(2), 17–23 (2015)
Göös, M., Jain, R., Watson, T.: Extension complexity of independent set polytopes. In: 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pp. 565–572. IEEE (2016)
Kaibel, V.: Extended formulations in combinatorial optimization. arXiv preprint arXiv:1104.1023 (2011)
Khoshkhah, K., Theis, D.O.: Fooling sets and the spanning tree polytope. arXiv preprint arXiv:1701.00350 (2017)
Martin, R.K.: Using separation algorithms to generate mixed integer model reformulations. Oper. Res. Lett. 10(3), 119–128 (1991)
Rothvoß, T.: The matching polytope has exponential extension complexity. In: STOC 2014–Proceedings of 2014 ACM Symposium on Theory of Computing, pp. 263–272. ACM, New York (2014)
Roughgarden, T.: Communication complexity (for algorithm designers). arXiv preprint arXiv:1509.06257 (2015)
Schrijver, A.: Combinatorial Optimization. Polyhedra and Efficiency. Springer, Heidelberg (2003)
Tuza, Z.: Covering of graphs by complete bipartite subgraphs: complexity of 0-1 matrices. Combinatorica 4(1), 111–116 (1984)
Wong, R.T.: Integer programming formulations of the traveling salesman problem. In: Proceedings of 1980 IEEE International Conference on Circuits and Computers, pp. 149–152 (1980)
Yannakakis, M.: Expressing combinatorial optimization problems by linear programs. J. Comput. System Sci. 43(3), 441–466 (1991)
Acknowledgement
We thank Monique Laurent and Ronald de Wolf for bringing the topic of this paper to our attention. We also acknowledge support from ERC grant FOREFRONT (grant agreement no. 615640) funded by the European Research Council under the EU’s 7th Framework Programme (FP7/2007-2013) and Ambizione grant PZ00P2 154779 Tight formulations of 0–1 problems funded by the Swiss National Science Foundation. Finally, we also thank the five anonymous referees for their constructive comments.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Aprile, M., Faenza, Y., Fiorini, S., Huynh, T., Macchia, M. (2017). Extension Complexity of Stable Set Polytopes of Bipartite Graphs. In: Bodlaender, H., Woeginger, G. (eds) Graph-Theoretic Concepts in Computer Science. WG 2017. Lecture Notes in Computer Science(), vol 10520. Springer, Cham. https://doi.org/10.1007/978-3-319-68705-6_6
Download citation
DOI: https://doi.org/10.1007/978-3-319-68705-6_6
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-68704-9
Online ISBN: 978-3-319-68705-6
eBook Packages: Computer ScienceComputer Science (R0)