Source-linked AI summary
The matching polytope has exponential extension complexity
Thomas Rothvoss
TL;DR
The paper asks whether the perfect matching polytope admits a polynomial-size linear formulation despite its efficient optimization and structured facet description. It develops a slack-matrix-based lower-bound approach and proves exponential extension complexity for perfect matching, with a corresponding strengthened bound for TSP.
Problem
The central open question is whether the perfect matching polytope can be represented by an LP with polynomially many constraints.
Method
The paper reduces extension-complexity lower bounds to nonnegative rank of the slack matrix and develops arguments addressing limitations of rectangle coverings.
Results
2^Ω(n) is the extension complexity of the perfect matching polytope in a complete n-node graph, and also of the TSP polytope.
Takeaways & Limitations
Polynomial-size exact extended formulations do not exist for the perfect matching and TSP polytopes in the stated complete-graph settings.
Takeaways & Limitations
For constant ε, the gap between known upper and lower bounds for approximate matching-polytope formulations remains huge.
Abstract
from arXiv · showhide
A popular method in combinatorial optimization is to express polytopes P, which may potentially have exponentially many facets, as solutions of linear programs that use few extra variables to reduce the number of constraints down to a polynomial. After two decades of standstill, recent years have brought amazing progress in showing lower bounds for the so called extension complexity, which for a polytope P denotes the smallest number of inequalities necessary to describe a higher dimensional polytope Q that can be linearly projected on P. However, the central question in this field remained wide open: can the perfect matching polytope be written as an LP with polynomially many constraints? We answer this question negatively. In fact, the extension complexity of the perfect matching polytope in a complete n-node graph is 2^Omega(n). By a known reduction this also improves the lower bound on the extension complexity for the TSP polytope from 2^Omega(n^1/2) to 2^Omega(n).
1 Introduction
The paper establishes exponential extension-complexity lower bounds for structured matching polytopes, resolving the perfect matching question and strengthening the corresponding TSP bound.
- 1 Introduction: Extension complexity measures the smallest number of facets in a higher-dimensional polyhedron that linearly projects onto the target polytope.A polynomial bound is called a compact formulation.
- 1 Introduction: The paper places its result within recent progress on exponential lower bounds, following earlier symmetric lower bounds and breakthrough results for the correlation and TSP polytopes.It contrasts those results with structured polytopes such as matchings, which admit polynomial-time optimization.
- 1 Introduction: The approach lower-bounds nonnegative slack-matrix rank and uses reductions from hard polytopes through faces and linear projections.The paper also analyzes why straightforward rectangle-covering arguments fail because large slack entries become over-covered.
- 1 Introduction: The perfect matching polytope is efficiently optimizable and has a complete inequality description using degree, odd-cut, and non-negativity constraints.Only polynomially many degree and non-negativity constraints are needed, while the odd-cut inequalities number 2^Ω(n).
- 1.1 Our contribution: 2^Ω(n) is the extension complexity of the perfect matching polytope in the complete n-node graph for even n.This is the paper’s main theorem, answering an open question about polynomial-size formulations.
- 1.1 Our contribution: 2^Ω(n) is also the extension complexity of the TSP polytope for Hamiltonian cycles in a complete n-node graph.The result improves the previously known 2^Ω(√n) lower bound.
2 Our approach
The approach converts extension-complexity lower bounds into non-negative-rank lower bounds for slack matrices, then uses hyperplane separation to show exponentially small rectangle contributions for the perfect matching polytope.
- Slack matrices and non-negative rank: Extension complexity equals the non-negative rank of a polytope’s slack matrix.This identifies the geometric quantity with an algebraic factorization measure.
- Slack matrices and non-negative rank: A non-negative factorization with r factors yields an extended formulation with r additional variables.The construction uses Q = {(x, y) | Ax + Uy = b, y ≥ 0} and projects onto x.
- Why rectangle covering fails: Rectangle covering lower bounds extension complexity, but the natural O(n^4)-rectangle covering for odd-set slack does not work.Entries with slack k are covered Θ(k^2) times rather than k times, so the induced rank-1 sum over-covers large slacks.
- Hyperplane separation: The authors instead use a hyperplane separation bound: a matrix W with large inner product with the slack matrix but small inner product on every rectangle implies a large extension complexity.The perfect matching slack matrix is restricted to odd-set inequalities because degree and non-negativity constraints are polynomially many.
- Hyperplane separation: For sufficiently large odd constant k, every rectangle has inner product at most 2^-δn with W, where δ = δ(k) > 0.The construction considers perfect matchings and t-node cuts, with parity forcing even intersection classes to have zero measure.
3 The quadratic measure increase
The technical ingredient compares measures of rectangles under three-edge and k-edge intersections, establishing a quadratic increase bound that yields the required exponential separation.
- Measure comparison: Lemma 7 bounds µ3(R) for every rectangle with µ1(R) = 0.This relation is the key measure comparison used to prove the main rectangle bound.
- Measure comparison: The resulting estimate implies the hyperplane-separation bound when k is a sufficiently large constant, such as k = 501.The proof uses that m is linear in n.
3.1 The concept of partitions
The partition construction organizes vertices into blocks so that selected matchings and cuts respect a common structure, restricting their crossing edges to C ∪ D.
- Partition structure: A partition T divides V into A, C, D, and B, with A and B further decomposed into m blocks.Each Ai has k − 3 nodes, each Bi has 2(k − 3) nodes, and C and D each have k nodes.
- Partition structure: E(T) consists of the edges lying inside the Bi blocks associated with T.This edge set is the structural component visualized for each partition.
- Respecting the partition: M(T) contains perfect matchings whose edges stay within Ai, Bi, or C ∪ D.These are the matchings that respect the partition.
- Respecting the partition: U(T) contains t-node cuts contained in A ∪ C that include either all or none of each Ai.Thus the selected cuts respect the same block structure as the matchings.
- Respecting the partition: For M ∈ M(T) and U ∈ U(T), δ(U) ∩ M lies entirely in E(C ∪ D) and has an odd size between 1 and k.This restriction enables comparisons between the relevant intersection measures.
3.2 Generating the distributions µ3 and µk
Uniform entries in Q3 and Qk are generated by first choosing a random partition, then a matching between C and D, and finally extending it to a respecting perfect matching and cut.
- Partition-induced distributions: The partition method compares µ3(R) and µk(R) through rectangles induced by each partition T.The comparison is the central probabilistic device for the measure bound.
- Conditional probabilities: The quantities pM,T, pexM,T, pU,T, and pexU,T record rectangle-membership probabilities under ordinary or exclusive conditioning.For cuts, the relevant C-node subset can have size only 3 or k.
- Generating Q3: A 3-matching H ⊆ C × D generates a uniform Q3 entry after random extension to M and U respecting T.The extensions satisfy M ∩ (C × D) = H and δ(U) ∩ (C × D) = H.
- Generating Qk: A k-matching F in C × D generates a uniform Qk entry after analogous extensions to M and U.The extensions enforce M ∩ (C × D) = F and δ(U) ∩ (C × D) = F.
3.3 The notion of good pairs
The section divides pairs into good, small, and bad categories and defines goodness through near-uniform matching and cut behavior. Small pairs have exponentially limited contribution, while the analysis separately controls good and bad pairs.
- Definitions: M-good pairs have conditional matching probabilities within a multiplicative 1 ± ε factor of a reference probability.Equivalently, their induced matching distribution is ε-close to uniform on the remaining nodes.
- Consequences: Goodness implies that all remaining edges are contained in at least one matching in M(T).The extension from pM,T to the relevant polytope contribution is handled after establishing the formal M-good property.
- Definitions: U-good pairs require that roughly half of compatible cuts contain the relevant part of C.The equivalent characterization gives a (1/2 ± Θ(ε))-fraction of such cuts.
- Classification: Pairs that are both M-good and U-good are called good, while pairs satisfying the contribution threshold 2^-δm are called small.Pairs that are neither good nor small are classified as bad.
- Decomposition: The measure μk(R) is split into contributions from good, small, and bad pairs, with ε chosen as a sufficiently small constant depending on k.The section then bounds these three contributions separately to establish the target inequality.
3.4 Contribution of good pairs
The contribution of good pairs is controlled by exploiting the structure of matchings and cuts. Two good pairs must overlap substantially, which limits how many 3-matchings can contribute positively.
- Contribution bound: The good-pair contribution is related to μk(R) through the matching and cut probabilities associated with a good pair.The section invokes the bounds established for M-good and U-good pairs.
- Contribution of good pairs: The core argument shows that only an O(1/k^2) fraction of 3-matchings H can contribute positively to the relevant expression.This is the section’s central combinatorial reason for the lack of a compact LP representation.
- Overlap structure: The overlap property bounds the number of good 3-matchings inside any fixed k-matching F.The proof derives this by ruling out pairs with intersection size at most one.
- Overlap structure: If two pairs (T,H) and (T,H*) are both good, then H and H* must share at least two edges.Otherwise, combining an edge from H\H* with H* would contradict the zero slack associated with the rectangle.
3.5 The pseudo-random behavior of large sets
Large families in product spaces exhibit pseudo-random coordinate behavior: most coordinates are nearly unbiased. Entropy bounds establish this phenomenon and its adaptation to fixed-weight cut distributions.
- Large families: A family X ⊆ 2^[m] of size at least 2^(1−ε)m has 99% of coordinates appearing in 50% ± 1% of its sets.This illustrates the pseudo-random behavior used later for compatible partitions.
- Entropy proof: The entropy proof shows that each ε-biased coordinate loses a fixed amount of entropy relative to the uniform distribution.Sub-additivity then prevents too many coordinates from being biased when the family is large.
- Application: The paper applies the large-family lemma twice: once to cuts and once to matchings.The cut case requires the fixed-weight modification, whereas the matching case uses the product-space formulation.
- Fixed-weight adaptation: Corollary 12 extends the unbiased-coordinate conclusion to fixed-weight vectors, despite the resulting distribution not being a product distribution.For the uniform weight-m/2 set, each coordinate still has marginal probability 1/2.
3.6 Contribution of bad pairs
The bad-pair analysis fixes a compatible pair and shows that only an ε-fraction of compatible partitions can remain bad. It treats cut-related and matching-related badness separately, using random partition constructions and pseudo-randomness.
- Setup: For every fixed (U,M) ∈ Q3, symmetry reduces the goal to proving that at most an ε-fraction of compatible partitions are bad.The cardinality of P(U,M) is identical for all pairs in Q3, allowing the expectations to be switched.
- Decomposition: Bad pairs are divided into U-bad and M-bad cases, according to whether cut or matching goodness fails.The two bounds are combined with a union bound to prove Lemma 13.
- U-bad pairs: For U-bad pairs, a two-phase random partition selects blocks and then randomly designates one block as the missing set C\V(H).The construction conditions on block containment, non-crossing, and cut-membership events.
- U-bad pairs: For a (1−ε/2)-fraction of indices, the corresponding partitions are U-good.The argument uses the large-family unbiasedness result to show that most candidate indices split the relevant cuts roughly evenly.
- M-bad pairs: For M-bad pairs, the construction partitions each ˜Bi into equal parts Ci and Di while conditioning that M* has no edge between them.The second phase again selects a random index, and unbiased indices yield M-good pairs.
- Conclusion: The completed bad-pair analysis proves Lemma 7 and thereby implies the paper’s main result.The proof separately controls the U-bad and M-bad contributions before combining them.
4 Inapproximability of the matching polytope
The section establishes exponential lower bounds for approximations to the matching polytope, extending earlier results across the full approximation-error spectrum while leaving a substantial constant-error gap.
- Approximation definition: The approximation guarantee is expressed equivalently through objective values: max{cx | x ∈ PM} ≤ max{cx | x ∈ K} ≤ (1 + ε)·max{cx | x ∈ PM}.This equivalence uses monotonicity of the matching polytope.
- Approximation lower bounds: For fixed 0 < α < 1, xc(K) ≥ 2^{cn} when PM ⊆ K ⊆ (1 + α)PM.The constant c = c(α) > 0 depends on α.
- Approximation lower bounds: xc(K) ≥ 2^Ω(min{1/ε,n}) for every polytope satisfying PM ⊆ K ⊆ (1 + ε)PM.This gives an exponential lower bound when ε is sufficiently small relative to 1/n, and a 2^Ω(1/ε) bound more generally.
- Proof strategy: The proof restricts an approximation K on G to an induced subgraph G′, preserving approximation and not increasing extension complexity.For a smaller graph, the effective error parameter becomes ε = 1/(2|V′|), enabling application of the earlier lower bound.
- Scope and limitations: The lower bound is fairly tight when ε ≪ 1/log n, but the gap between known upper and lower bounds remains large for constant ε.Earlier formulations using only small odd-cut inequalities motivate the comparison with compact approximations having many facets.