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?
$\begingroup$
$\endgroup$
4
-
2$\begingroup$ 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... $\endgroup$– JakobSCommented Jul 4, 2019 at 8:59
-
2$\begingroup$ @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. $\endgroup$– Kevin DalmeijerCommented Jul 8, 2019 at 21:03
-
3$\begingroup$ @JakobS also be cautious with statements "is in NP" because $P \subseteq NP$ ;) $\endgroup$– Marco LübbeckeCommented Jul 8, 2019 at 22:35
-
1$\begingroup$ @Kevin you're probably right... Marco, you're also right :) should have written NP-hard or NP-complete. $\endgroup$– JakobSCommented Jul 9, 2019 at 9:58
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
I think the spanning tree polytope also falls under this category. Computing the minimum spanning tree is easy. However, we would require all the sub-tour elimination constraints (which is exponential in number of vertices) to represent the spanning tree polytope in 0-1 variables as a LP.
EDIT:
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.
-
5$\begingroup$ I could be wrong, but I think MST can be formulated using a polynomial-sized MIP using a flow-based approach. $\endgroup$ Commented Aug 20, 2019 at 17:31
-
$\begingroup$ @LarrySnyder610 could you add a reference to this formulation? The two formulations I know of for this problem are the cutset and subtour elimination formulations (see, e.g., chapter 10.3 of Bertsimas and Tsitsiklis). They mention that separating over the STE formulation reduces to a minimum cut problem (meaning it can be solved in polynomial time by the ellipsoid method), which seems related to your comment; but the STE formulation has exponentially many constraints. $\endgroup$ Commented Aug 20, 2019 at 19:25
-
2$\begingroup$ @RyanCory-Wright This paper is for a variant of MST, and it uses a flow-based approach. I don't have a reference for plain MST to hand, but I'm pretty sure the idea is similar. $\endgroup$ Commented Aug 20, 2019 at 19:54
-
3$\begingroup$ @LarrySnyder610 is right, see e.g. (10)-(15) in Martin (1991) for an $O(n^3)$ formulation for MST. $\endgroup$ Commented Aug 21, 2019 at 4:40
-
$\begingroup$ Note also that the OP itself says that the MST can be formulated in polynomial size, so I shouldn't get the credit for pointing that out. Just for breaking the tie ;) $\endgroup$ Commented Aug 21, 2019 at 13:17