{"id":1603,"date":"2016-02-13T13:02:55","date_gmt":"2016-02-13T18:02:55","guid":{"rendered":"http:\/\/matroidunion.org\/?p=1603"},"modified":"2016-02-17T05:08:19","modified_gmt":"2016-02-17T10:08:19","slug":"extended-formulations-and-matroid-polytopes","status":"publish","type":"post","link":"https:\/\/matroidunion.org\/?p=1603","title":{"rendered":"Extended Formulations and Matroid Polytopes"},"content":{"rendered":"

For this post, I will give a brief introduction to the field of\u00a0extended formulations. \u00a0<\/em>This is a subject that is very much in vogue at the moment, with some outstanding recent breakthroughs that I will touch upon. \u00a0There are also a lot of nice matroidal results\u00a0in this area, a few of which I will mention here, together with some conjectures.<\/p>\n

The\u00a0TSP\u00a0<\/em>polytope,\u00a0TSP$(n) \\in \\mathbb{R}^{\\binom{n}{2}}$ is\u00a0the convex hull of the set of Hamiltonian cycles of the complete graph $K_n$. \u00a0The number of facets of\u00a0TSP$(n)$ grows extremely quickly with $n$. For example, TSP$(10)$ has more than $50$ billion facets. \u00a0The central question of extended formulations is:\u00a0what if we are looking at this problem in the wrong dimension? \u00a0<\/em>That is, could there be a simple polytope in a higher dimensional space that projects down to\u00a0the\u00a0TSP<\/em> polytope? \u00a0This motivates the notion of\u00a0extension complexity. \u00a0Given a polytope $P$, the extension complexity<\/em> of $P$, xc$(P)$ is<\/p>\n

$$\\min \\{ \\text{number of facets of $Q$: $Q$ projects to $P$}\\}.$$<\/p>\n

It may seem strange that increasing the dimension (adding more variables) can decrease the number of facets, but the following picture (thanks to Samuel Fiorini for permission to use it) shows that this is indeed possible.<\/p>\n

\"twistedcube\"<\/a><\/p>\n

In the 1980s, Swart [1] attempted to prove that there is a polytope with only polynomial many facets that projects down to the\u00a0TSP\u00a0<\/em>polytope. \u00a0Note that a polynomial size extended formulation for the TSP<\/em> polytope\u00a0would imply P=NP. \u00a0The purported linear programs were extremely\u00a0complicated to analyze. \u00a0However, in a breakthrough paper, Yannakakis [2] refuted all such attempts by showing that every symmetric<\/em> linear program (LP) for the\u00a0TSP<\/em> polytope has exponential size. \u00a0Here\u00a0symmetric<\/em> means that each permutation of the cities can be extended to a permutation of the variables without changing the LP. \u00a0Since all the proposed LPs of Swart were symmetric, that was the end of the story (for then).<\/p>\n

A lingering question however, was whether the symmetry condition was necessary. Yannakakis himself felt that\u00a0asymmetry should not really help much. \u00a0However, in 2010, Kaibel, Pashkovich, and Theis [3] gave examples of polytopes that do not have polynomial size symmetric extended formulations, but that do have polynomial size asymmetric extended formulations. \u00a0This rekindled interest in the lingering question. \u00a0In another breakthrough paper in 2012, Fiorini, Masser, Pokutta, Tiwary, and de Wolf [4] finally proved that the\u00a0TSP<\/em> polytope does not admit any polynomial size extended formulation,\u00a0symmetric or not.<\/em> \u00a0Their proof uses the\u00a0Factorization Theorem\u00a0<\/em>of\u00a0Yannakakis. That is, the extension complexity of a polytope is actually just the\u00a0non-negative rank of an associated matrix (called the slack matrix<\/em>). To show that this non-negative rank is large for TSP$(n)$, they use a combinatorial lemma due to Razborov [5].<\/p>\n

Of course, we can ask about the extension complexity of many other polytopes (including matroid polytopes) that arise in combinatorial optimization. \u00a0Another famous example\u00a0is the\u00a0perfect matching polytope,\u00a0<\/em>PM$(n)$, which is the convex hull of all perfect matchings of the complete graph $K_n$. \u00a0Note that we can optimize any linear objective function over the perfect matching polytope\u00a0in strongly polynomial time via Edmond’s maximum matching algorithm. \u00a0Thus, it was quite\u00a0surprising when Rothvo\u00df [6] showed that\u00a0PM$(n)$ does not admit any polynomial size extended formulation!<\/p>\n

Given a matroid $M$, the\u00a0independence polytope<\/em> of $M$ is the convex hull of all independent sets of $M$. \u00a0Rothvo\u00df [7] also proved that there exists a family of matroids such that their corresponding independence polytopes have extension complexity exponential in their dimension. \u00a0The fascinating thing about his proof, is that it is purely existential. That is, since it uses a counting argument for the number of matroids on $n$ elements due to\u00a0Knuth\u00a0[8], no explicit family of matroids is known. \u00a0Indeed, a nice recent observation<\/a> of Mika G\u00f6\u00f6s<\/a>\u00a0is that such an explicit family would imply the\u00a0existence of explicit non-monotone circuit depth lower bounds (which no one knows how to do at the moment).<\/p>\n

For positive results, Kaibel, Lee, Walter, and Weltge [9] showed that the independence polytopes of regular matroids have polynomial size extended formulations. \u00a0Their result uses Seymour’s Decomposition Theorem for regular matroids.<\/p>\n

Another class of matroids with small extension complexity are\u00a0sparsity matroids<\/em> (which I will now define). \u00a0Let $G$ be a graph and let $k$ and $\\ell$ be integers with $0 \\leq \\ell \\leq 2k-1$. We say that $G$ is $(k, \\ell)$-sparse\u00a0<\/em>if for all subsets of edges $F$, $|F| \\leq \\max \\{k|V(F)|-\\ell, 0\\}$, where $V(F)$ is the set of vertices covered by $F$. \u00a0$G$ is\u00a0$(k, \\ell)$-tight<\/em> if it is $(k, \\ell)$–<\/em>sparse and $|E(G)|=\\max \\{k|V(G)|-\\ell, 0\\}$. \u00a0Consider the\u00a0subsets of edges $F$ of $G$ such that the graph $(V(G), F)$ is\u00a0$(k, \\ell)$–<\/em>tight. \u00a0It turns out that such a collection of subsets is a matroid. Matroids arising in this way are called\u00a0$(k, \\ell)$-sparsity matroids. \u00a0<\/em>Note that graphic matroids are $(1,1)$-sparsity matroids. \u00a0Iwata, Kamiyama, Katoh, Kijima, and Okamoto [10] recently proved that sparsity matroids have polynomial size extended formulations.<\/p>\n

Both these examples are in some sense close to graphic matroids. \u00a0It may be that being ‘close’ to graphic is a sufficient condition for having\u00a0compact extended formulations. Indeed, as far as I know the following conjectures are all open.<\/p>\n

Conjecture 1.<\/strong>\u00a0 The independence polytopes of signed graphic and even cycle matroids both have polynomial size extended formulations.<\/p>\n

Conjecture 2.<\/strong> \u00a0The independence polytopes of a proper minor-closed class of binary matroids have polynomial size extended formulations.<\/p>\n

Conjecture 3.\u00a0<\/strong>\u00a0The independence polytopes of binary matroids have polynomial size extended formulations.<\/p>\n

Conjecture 4. \u00a0<\/strong>For each finite field $\\mathbb{F}$, the independence polytopes of $\\mathbb{F}$-representable matroids have polynomial size extended formulations.<\/p>\n

References.<\/strong><\/p>\n

[1]\u00a0E. R. Swart. P = NP. Technical report<\/em>, University of Guelph, 1986; revision 1987.<\/p>\n

[2]\u00a0M. Yannakakis. Expressing combinatorial optimization problems by linear programs (extended abstract). In Proc. STOC 1988<\/em>, pages 223\u2013228, 1988.<\/p>\n

[3]\u00a0V. Kaibel, K. Pashkovich, and D.O. Theis. Symmetry matters for the sizes of extended formulations. In Proc. IPCO 2010<\/em>, pages 135\u2013148, 2010.<\/p>\n

[4] S. Fiorini, S. Massar, S. Pokutta, H. Tiwary, and R. de Wolf. Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds. In STOC<\/em>, pages 95\u2013106, 2012.<\/p>\n

[5]\u00a0A. A. Razborov. On the distributional complexity of disjointness. Theoret. Comput. Sci<\/em>., 106(2):385\u2013 390, 1992.<\/p>\n

[6] T.Rothvo\u00df. The matching polytope has exponential extension complexity, In STOC<\/em>, New York, NY, USA, 2014, ACM, pp. 263\u2013272.<\/p>\n

[7]\u00a0T.Rothvo\u00df. Some 0\/1 polytopes need exponential size extended formulations, Math. Program. Ser. A<\/em>, (2012), pp. 1\u201314.<\/p>\n

[8] D. E. Knuth.<\/span>\u00a0The asymptotic number of geometries, J. Combinatorial Theory Ser. A<\/em> 16 (1974), 398\u2013400.<\/p>\n

[9]\u00a0Kaibel, V., Lee, J., Walter, M., & Weltge, S. (2015). Extended Formulations for Independence Polytopes of Regular Matroids. <\/span>arXiv preprint arXiv:1504.03872<\/i>.<\/span><\/p>\n

[10]\u00a0Iwata, S., Kamiyama, N., Katoh, N., Kijima, S., & Okamoto, Y. (2015). Extended formulations for sparsity matroids. Mathematical Programming<\/i>, 1-10.<\/p>\n","protected":false},"excerpt":{"rendered":"

For this post, I will give a brief introduction to the field of\u00a0extended formulations. \u00a0This is a subject that is very much in vogue at the moment, with some outstanding recent breakthroughs that I will touch upon. \u00a0There are also … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":10,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-1603","post","type-post","status-publish","format-standard","hentry","category-matroids"],"_links":{"self":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/1603","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/users\/10"}],"replies":[{"embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1603"}],"version-history":[{"count":49,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/1603\/revisions"}],"predecessor-version":[{"id":1656,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/1603\/revisions\/1656"}],"wp:attachment":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1603"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1603"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1603"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}