zbMATH — the first resource for mathematics

On the extension complexity of combinatorial polytopes. (English) Zbl 1336.90095
Summary: 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.

90C35 Programming involving graphs or networks
90C60 Abstract computational complexity for mathematical programming problems
PDF BibTeX Cite
Full Text: DOI arXiv
[1] Avis, D; Imai, H; Ito, T; Sasaki, Y, Two-party Bell inequalities derived from combinatorics via triangular elimination, J. Phys. A Math. Gen., 38, 10971-10987, (2005) · Zbl 1092.81508
[2] Avis, D; Imai, H; Ito, T, Generating facets for the cut polytope of a graph by triangular elimination, Math. Program., 112, 303-325, (2008) · Zbl 1190.90281
[3] Barahona, F.: The max-cut problem on graphs not contractible to \({K}_{5}\). Oper. Res. Lett. 2(3), 107-111 (1983). ISSN 0167-6377 · Zbl 0525.90094
[4] Bell, JS, On the Einstein-Podolsky-Rosen paradox, Physics, 1, 195-290, (1964)
[5] Corman, T.H., Leiserson, C. E., Rivest, R. L.: Introduction to Algorithms. MIT Press, Cambridge, MA (2009). ISBN 0-262-03141-8
[6] de Wolf, R.: Nondeterministic quantum query and communication complexities. SICOMP. SIAM J. Comput. 32, 681-699 (2003) · Zbl 1026.68055
[7] Deza, M.M., Laurent, M.: Geometry of Cuts and Metrics, Volume 15 of Algorithms and Combinatorics. Springer, Berlin (1997) · Zbl 0885.52001
[8] 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) · Zbl 1286.90125
[9] Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, San Francisco, CA (1979) · Zbl 0411.68039
[10] Garey, MR; Johnson, DS; Stockmeyer, LJ, Some simplified NP-complete graph problems, Theor. Comput. Sci., 1, 237-267, (1976) · Zbl 0338.05120
[11] Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85-103. Plenum Press, New York (1972)
[12] Pokutta, S., Vyve, M.V.: A note on the extension complexity of the knapsack polytope. Optimization Online (2013) · Zbl 1286.90168
[13] Razborov, AA, On the distributional complexity of disjointness, Theor. Comput. Sci., 106, 385-390, (1992) · Zbl 0787.68055
[14] Yannakakis, M, Expressing combinatorial optimization problems by linear programs, J. Comput. Syst. Sci., 43, 441-466, (1991) · Zbl 0748.90074
[15] Ziegler, G.M.: Lectures on Polytopes, Volume 152 of Graduate Texts in Mathematics. Springer, Berlin (1995) · Zbl 0823.52002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.