# Polynomially solvable problems with exponential extension complexity

The maximum matching problem is solvable in polynomial time using Edmonds' blossom algorithm. However, unlike for example the spanning tree polytope, it has been proven fairly recently that the matching polytope has exponential extension complexity, meaning that it cannot be represented by a polynomially sized linear program Rothvoss (2017). I think this is a very interesting result, as it illustrates the limitations of expressing problems as linear programs. My question: are there any other problems that are solvable in polynomial time but whose polytopes have exponential extension complexity?

• I think you have to consider the "direction" of the problem: Computing the shortest path is polynomial solvable while the longest path is in NP. The underlying polytope is the same but you look at different directions of the polytope. Roughly speaking, for a problem to be solvable in polytime it is sufficient to have a "nice" representation of the relevant part of the polytope. Same applies for other problems, for example min and max cut... Jul 4 '19 at 8:59
• @JakobS I am not sure this is correct. For the longest path problem, the underlying polytope is that of the simple paths. The shortest path polytope also contains non-simple paths. These are just never selected if all cycles are non-negative. Jul 8 '19 at 21:03
• @JakobS also be cautious with statements "is in NP" because $P \subseteq NP$ ;) Jul 8 '19 at 22:35
• @Kevin you're probably right... Marco, you're also right :) should have written NP-hard or NP-complete. Jul 9 '19 at 9:58

From the comments below, one can find a reference for a polynomial characterization of the spanning tree polytope. So my answer that the spanning tree has $$$$exponential extension complexity" is incorrect. I will however let this answer remain because I think not many people are aware of polynomial formulations for the spanning tree polytope. The edit is meant to notify people who read this post, not to overlook that fact.
• @LarrySnyder610 is right, see e.g. (10)-(15) in Martin (1991) for an $O(n^3)$ formulation for MST. Aug 21 '19 at 4:40