Finding a perfect matching using an LP

Question

I have a basic question about the power of Linear Programming that has been bothering me for some time. I believe there is something simple I am missing.

Linear Programming is $\mathsf{P}$-complete, which means that every problem in $\mathsf{P}$ can be reduced to it using an $\mathsf{NC}$ reduction. (See the wiki for some nice background)

However, it has been shown that the perfect matching polytope has exponentially many facets (see this recent STOC paper for example. This shows it even has exponential extension complexity---i.e. even using extra dimensions we require an exponential number of inequalities).

However, the classic Blossom Algorithm can find a perfect matching in polynomial time--determining if a graph has a perfect matching is in $\mathsf{P}$.

This seems like a conflict to me: we can reduce the perfect matching problem to Linear Programming, but its polytope must be exponentially large. What am I mising? Is there processing during the reduction that avoids using the entire matching polytope?

Answer 1

The lower bounds on extended formulations (the one by Rothvoss for example) are lower bounds for a very specific way of using Linear Programming to solve a problem (matching in this case).

In this model, given a graph you would like to write one linear program, changing whose objective function gives you the right matching corresponding to any weight function on the given graph. This requirement results in the restriction that the feasible region of such an LP must project down to the matching polytope. The lower bound is not immediately applicable if you provide different LPs for different weights, or you use the objective function in a non-trivial way. (Note that in this model, we use the weights on the edges as the objective function without any modification)

Allowing different LPs for different weights obviously breaks the result: First solve the weighted problem and then produce a trivial LP whose feasible region contains exactly one point (the answer). This LP would trivially have small size.

Now, you can argue similarly that allowing weights to be manipulated arbitrarily allows you to "cheat" and write small LPs too.

The discussion about P-completeness of Linear Programming becomes interesting if you ask the following.

Q: Can you use Linear Programming to solve the matching problem in a "black box" fashion "with minimal extra computation"?

The answer in this case is yes, and the extra computation turns out to be just encoding the input graph in a trivial way as the objective function (by essentially taking the characteristic vector of edges with encoding digits +/-1 instead of 0/1). This extra computation seems reasonable and so the LP encoding of the matching problem in this case seems interesting. The LP in this case turns out to be of small size precisely because matching is in P and Linear Programming is P-complete.