For this post, I will give a brief introduction to the field of extended formulations. This is a subject that is very much in vogue at the moment, with some outstanding recent breakthroughs that I will touch upon. There are also a lot of nice matroidal results in this area, a few of which I will mention here, together with some conjectures.
The TSP polytope, TSP$(n) \in \mathbb{R}^{\binom{n}{2}}$ is the convex hull of the set of Hamiltonian cycles of the complete graph $K_n$. The number of facets of TSP$(n)$ grows extremely quickly with $n$. For example, TSP$(10)$ has more than $50$ billion facets. The central question of extended formulations is: what if we are looking at this problem in the wrong dimension? That is, could there be a simple polytope in a higher dimensional space that projects down to the TSP polytope? This motivates the notion of extension complexity. Given a polytope $P$, the extension complexity of $P$, xc$(P)$ is
$$\min \{ \text{number of facets of $Q$: $Q$ projects to $P$}\}.$$
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.
In the 1980s, Swart [1] attempted to prove that there is a polytope with only polynomial many facets that projects down to the TSP polytope. Note that a polynomial size extended formulation for the TSP polytope would imply P=NP. The purported linear programs were extremely complicated to analyze. However, in a breakthrough paper, Yannakakis [2] refuted all such attempts by showing that every symmetric linear program (LP) for the TSP polytope has exponential size. Here symmetric means that each permutation of the cities can be extended to a permutation of the variables without changing the LP. Since all the proposed LPs of Swart were symmetric, that was the end of the story (for then).
A lingering question however, was whether the symmetry condition was necessary. Yannakakis himself felt that asymmetry should not really help much. However, 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. This rekindled interest in the lingering question. In another breakthrough paper in 2012, Fiorini, Masser, Pokutta, Tiwary, and de Wolf [4] finally proved that the TSP polytope does not admit any polynomial size extended formulation, symmetric or not. Their proof uses the Factorization Theorem of Yannakakis. That is, the extension complexity of a polytope is actually just the non-negative rank of an associated matrix (called the slack matrix). To show that this non-negative rank is large for TSP$(n)$, they use a combinatorial lemma due to Razborov [5].
Of course, we can ask about the extension complexity of many other polytopes (including matroid polytopes) that arise in combinatorial optimization. Another famous example is the perfect matching polytope, PM$(n)$, which is the convex hull of all perfect matchings of the complete graph $K_n$. Note that we can optimize any linear objective function over the perfect matching polytope in strongly polynomial time via Edmond’s maximum matching algorithm. Thus, it was quite surprising when Rothvoß [6] showed that PM$(n)$ does not admit any polynomial size extended formulation!
Given a matroid $M$, the independence polytope of $M$ is the convex hull of all independent sets of $M$. Rothvoß [7] also proved that there exists a family of matroids such that their corresponding independence polytopes have extension complexity exponential in their dimension. The 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 Knuth [8], no explicit family of matroids is known. Indeed, a nice recent observation of Mika Göös is that such an explicit family would imply the existence of explicit non-monotone circuit depth lower bounds (which no one knows how to do at the moment).
For positive results, Kaibel, Lee, Walter, and Weltge [9] showed that the independence polytopes of regular matroids have polynomial size extended formulations. Their result uses Seymour’s Decomposition Theorem for regular matroids.
Another class of matroids with small extension complexity are sparsity matroids (which I will now define). Let $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 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$. $G$ is $(k, \ell)$-tight if it is $(k, \ell)$–sparse and $|E(G)|=\max \{k|V(G)|-\ell, 0\}$. Consider the subsets of edges $F$ of $G$ such that the graph $(V(G), F)$ is $(k, \ell)$–tight. It turns out that such a collection of subsets is a matroid. Matroids arising in this way are called $(k, \ell)$-sparsity matroids. Note that graphic matroids are $(1,1)$-sparsity matroids. Iwata, Kamiyama, Katoh, Kijima, and Okamoto [10] recently proved that sparsity matroids have polynomial size extended formulations.
Both these examples are in some sense close to graphic matroids. It may be that being ‘close’ to graphic is a sufficient condition for having compact extended formulations. Indeed, as far as I know the following conjectures are all open.
Conjecture 1. The independence polytopes of signed graphic and even cycle matroids both have polynomial size extended formulations.
Conjecture 2. The independence polytopes of a proper minor-closed class of binary matroids have polynomial size extended formulations.
Conjecture 3. The independence polytopes of binary matroids have polynomial size extended formulations.
Conjecture 4. For each finite field $\mathbb{F}$, the independence polytopes of $\mathbb{F}$-representable matroids have polynomial size extended formulations.
References.
[1] E. R. Swart. P = NP. Technical report, University of Guelph, 1986; revision 1987.
[2] M. Yannakakis. Expressing combinatorial optimization problems by linear programs (extended abstract). In Proc. STOC 1988, pages 223–228, 1988.
[3] V. Kaibel, K. Pashkovich, and D.O. Theis. Symmetry matters for the sizes of extended formulations. In Proc. IPCO 2010, pages 135–148, 2010.
[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, pages 95–106, 2012.
[5] A. A. Razborov. On the distributional complexity of disjointness. Theoret. Comput. Sci., 106(2):385– 390, 1992.
[6] T.Rothvoß. The matching polytope has exponential extension complexity, In STOC, New York, NY, USA, 2014, ACM, pp. 263–272.
[7] T.Rothvoß. Some 0/1 polytopes need exponential size extended formulations, Math. Program. Ser. A, (2012), pp. 1–14.
[8] D. E. Knuth. The asymptotic number of geometries, J. Combinatorial Theory Ser. A 16 (1974), 398–400.
[9] Kaibel, V., Lee, J., Walter, M., & Weltge, S. (2015). Extended Formulations for Independence Polytopes of Regular Matroids. arXiv preprint arXiv:1504.03872.
[10] Iwata, S., Kamiyama, N., Katoh, N., Kijima, S., & Okamoto, Y. (2015). Extended formulations for sparsity matroids. Mathematical Programming, 1-10.
Hi Tony,
what a great post. This extension rank could of great interest, I think.
1) I remember the argument from [7], that independence polytopes cannot all have small extension rank, like this: there are many matroids => there are many extended formulations of matroid independence polytopes => these extended formulations cannot all have small rank. So that is not really existential, but starts with an explicit construction of many (sparse paving) matroids. What it has in common with [8] is the making of a `compressed description’ of matroids, but where we use this to prove that there are few matroids, he uses his compression in reverse to show that the `size’ of his description is not uniformly small.
2) er(M):=`extension rank of the independence polytope of M’ looks like it could be a very useful complexity measure for matroids. It certainly outperforms the `cover complexity’ of Jorn and me on graphic matroids. I wonder if it shares these nice properties with cover complexity:
a) er(M\e) \le er(M)
b) er(M/e) \le er(M)
c) er(M) \le er(M/e)+er(M\e)
It would be great if you could put bounds on er(M) in terms of max{ er(N): N minor of M, rank(N)=s}.
3) there is a very interesting general relation between extension rank and communication protocols, which boils down to this for matroids:
The following are equivalent:
a) er(M)\le k
b) there is a randomized communication protocol for M that involves the exchange of at most log(k) bits between two parties, X and Y, so that if X is given a basis B of M and Y a flat F of M, then the protocol will produce an estimate for |F\cap B| whose average value is the actual value (X and Y may use random bits in the execution of the protocol).
I can’t find the reference for this right now, but I’ll be back.
Hi Rudi. Thanks for your comments! Regarding 3b, the reference is Extended formulations, nonnegative factorizations, and randomized communication protocols by Y. Faenza, S. Fiorini, R. Grappe, and H. R. Tiwary. The general method of ‘computing the slack matrix in expectation’ works to obtain upper bounds on the extension complexity of any polytope. For matroid independence polytopes, if you write down the slack matrix, the randomized communication protocol does precisely what you said.
Yes, that was the reference.
Now that I see that paper again, I have to correct my statement 3b. The protocol must not compute |B\cap F|, but rather the slack s(F,B):=rank(F)-|F\cap B|, and it is a restriction that the protocol may only output a nonnegative estimate of s(F,B). This makes a difference!
The paper contains a description of a communication protocol for graphic matroids. Recommended reading.
So to prove your Conjecture 4, it would suffice to show that for a GF(q)-representable matroid on n elements, the exchange of at most O(log(n)) bits suffices to compute the slack s(F,B) in expectation.
So the answer to 2a and 2b are yes (see the other conversation thread). I think the answer to 2c is also yes via Balas’ union of polyhedra trick. That is, the extension complexity of the union two polytopes P and Q is at most xc(P)+xc(Q). In the case of matroid polytopes, the matroid polytope of M is the union of the matroid polytopes of M / e and M \ e (as can be seen by conditioning if e is in your independent set or not).
Excellent!
Does that `union of polytopes’ trick also prove the following:
“Suppose M is a matroid of rank r and X_1, .. , X_k are sets of size t so that each subset of E(M) of cardinality r contains exactly one of these sets. Then xc(M)\le sum_i xc(M/X_i)”
For any fixed r there are such X_i provided |E(M)| is large enough, so that would show for a matroid M on n elements of rank r and a t\le r that:
xc(M)/(n choose r) \le
max{xc(N): N minor of M, r(N)=r-t} / (n-t choose r-t)
I conjecture that this even holds for small n.
Interesting question. What is the source of belief in the conjectures?
Don’t conjectures 1 and 4 contradict each other? At least for signed graphic matroids?
Thanks for your comment. I don’t see why Conjectures 1 and 4 contradict each other. Signed graphic matroids are ternary, but Conjectures 1 and 4 assert that both classes have compact extended formulations. The conjectures are based on the positive results thus far for ‘graphic like’ matroids. The classes get ‘less graphic’ as you progress from Conjectures 1 to 4, so it may very well be that Conjectures 3 and 4 are false (or they all may be false).
Sorry, somehow I read a negation into Conjecture 1. It makes a lot more sense now.
Next question… is it immediate whether having a polynomial-sized extended formulation is closed under taking minors?
Yes, I think this is clear. If N is a minor of M, then the independence polytope of N is a coordinate projection of a face of the independence polytope of M. Therefore, the extension complexity of N is at most the extension complexity of M.
Does the extension complexity go down by exactly 1 if you relax a circuit-hyperplane?
Edit: Hmm, that can’t be true. A graph may have exponentially many circuit-hyperplanes. Second try:
Does the extension complexity go down, or stay the same, if you relax a circuit-hyperplane?
To me it seems that complexity is hardly closed under minors. If i have a set of matroids (or graphs) and an algorithm that solves some problem on that set. Now take a a minor M of a member M’ in that class. How to to apply a the algorithm If M’ is too big.
Example: stable set problem on graphs with n notes and a clique of size n-log n is polynomilally solvable as there are only polynomially many stable sets. But if you close the class under induced subgraphs you get all graphs. You know for any input graph it is in the class, so membership of the input is not the issue, the issue is that the algorithm needs an input that is too big. For matroids and extended formulations similar examples exist.
The sense in complexity issues for minor closed classes doesn not lie in the minor-closedness, but on some tangible structure that comes with the class.
Where I wrote:
“The sense in complexity issues for minor closed classes does not lie in the minor-closedness, but on some tangible structure that comes with the class”,
it would have been more to the point to write:
The sense in complexity issues for proper minor closed classes doesn not lie in the minor closedness but in the properness.
Hi Bert,
Extension complexity of M is not a measure of how fast decision problems concerning M can be solved, but how much bits it takes to describe M.
If you allow the most generally capable machine to reconstruct the matroid M from your description, then this smallest length of the description is just the Kolmogorov complexity of M.
Here the description has to take the form of an extended formulation of the independence polytope. So that is a very restricted machine, but it is still surprisingly good at picking up the graphic structure of a matroid.
You expect from a good complexity measure that it is roughly minor-monotone. A Kolmogorov string describing a minor N of M could always say: here’s a description of M and here is how you get me as a minor. The latter is going to be few bits compared to the bits it takes to describe a matroid M.
In the same way, you would also expect that the sum of the complexities of M/e and M\e is an upper bound for the complexity of M. Perhaps Tony can show that too for the extension complexity.
Hi Bert! Thanks for the comment. Yes, you are absolutely correct. I realize that I was not answering the question that was asked. While it is true that extension complexity is minor monotone, the number of elements also decreases as you pass to minors so the new class that you get from closing your class under minors might not have polynomial size extension complexity even if your original class does. For example, I think binary projective geometries have small extension complexity (at most quasi-polynomial). However, if you close this class under minors, you get all binary matroids. I can imagine that this class might have large extension complexity (even though I conjectured otherwise above).
Rudi,
I know extension complexity is not about how quick the problem can be solved. My point was that complexity of any kind is generally not closed under minors.
I gave an example concerning computational complexity of stable sets and the induced subgraph order as I found that eassier to explain.
For matroids on n elements with a component isomorphic to a n-log n point line, even the matroid polytope itself has polynomially many
If you close that class under minors you get all matroids. As long as you do not calculate the input size for ‘that class’ after adding the huge line, your lost
Best,
Bert
I realized that I misread your words the minute I read Tony’s reply. Sorry about that 🙂 You made a valid point!