Abstract
In this paper we extend recent results of Fiorini et al. on the extension complexity of the cut polytope and related polyhedra. We first describe a lifting argument to show exponential extension complexity for a number of NP-complete problems including subset-sum and three dimensional matching. We then obtain a relationship between the extension complexity of the cut polytope of a graph and that of its graph minors. Using this we are able to show exponential extension complexity for the cut polytope of a large number of graphs, including those used in quantum information and suspensions of cubic planar graphs.
Due to space constraints many proofs have been omitted here. A full version containing all proofs is available at http://arxiv.org/abs/1302.2340
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Avis, D., Imai, H., Ito, T.: Generating facets for the cut polytope of a graph by triangular elimination. Math. Program. 112(2), 303–325 (2008)
Avis, D., Imai, H., Ito, T., Sasaki, Y.: Two-party bell inequalities derived from combinatorics via triangular elimination. J. Phys. A: Math. General 38(50), 10971–10987 (2005)
Barahona, F.: The max-cut problem on graphs not contractible to \({K}\sb{5}\). Oper. Res. Lett. 2(3), 107–111 (1983)
Bell, J.S.: On the Einstein-Podolsky-Rosen paradox. Physics 1(3), 195–290 (1964)
Conforti, M., Cornuéjols, G., Zambelli, G.: Extended formulations in combinatorial optimization. 4OR 8, 1–48 (2010)
Corman, T.H., Leiserson, C.E., Rivest, R.L.: Introduction to Algorithms. MIT Press (2009)
Deza, M.M., Laurent, M.: Geometry of cuts and metrics. Algorithms and Combinatorics, vol. 15. Springer (1997)
Fiorini, S., Massar, S., Pokutta, S., Tiwary, H.R., de Wolf, R.: Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds. In: STOC, pp. 95–106 (2012)
Garey, M.R., Johnson, D.S.: Computers and intractability; a guide to the theory of NP-completeness. W.H. Freeman (1979)
Garey, M.R., Johnson, D.S., Stockmeyer, L.J.: Some simplified NP-complete graph problems. Theoret. Comput. Sci. 1, 237–267 (1976)
Karp, R.M.: Reducibility among combinatorial problems. In: Miller, Tatcher (eds.) Complexity of Computer Computations. Plenum (1974)
Rothvoß, T.: Some 0/1 polytopes need exponential size extended formulations. arXiv:1105.0036 (2011)
Yannakakis, M.: Expressing combinatorial optimization problems by linear programs. Journal of Computer and System Sciences 43(3), 441–466 (1991)
Ziegler, G.M.: Lectures on polytopes. Graduate Texts in Mathematics, vol. 152. Springer (1995)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Avis, D., Tiwary, H.R. (2013). On the Extension Complexity of Combinatorial Polytopes. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds) Automata, Languages, and Programming. ICALP 2013. Lecture Notes in Computer Science, vol 7965. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-39206-1_6
Download citation
DOI: https://doi.org/10.1007/978-3-642-39206-1_6
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-39205-4
Online ISBN: 978-3-642-39206-1
eBook Packages: Computer ScienceComputer Science (R0)