The matching polytope does not admit fully-polynomial size relaxation schemes

Gábor Braun, Sebastian Pokutta

Abstract

The matching polytope is a central object in combinatorial optimization. While the matching problem is solvable in polynomial time, recent breakthroughs established that its linear programming (LP) extension complexity is exponential. This paper generalizes these results to the regime of approximation, proving that any LP relaxation providing a $(1 + \varepsilon/n)$-approximation of the matching polytope requires an exponential number of inequalities. This identifies matching as the first problem in P that does not admit a fully-polynomial size relaxation scheme (FPSRS), providing a sharp separation between constant-factor approximations and high-precision relaxations.

Introduction

In computational complexity, we typically categorize problems based on the time required for an algorithm to find an optimal solution. However, another crucial metric is extension complexity: the minimum number of inequalities required to represent a problem's feasible region as a linear program (LP).

For many years, it was an open question whether problems in P—those solvable in polynomial time—always possessed polynomial-sized LP representations. This was famously answered in the negative by Rothvoß (2013), who proved that the matching polytope (the convex hull of all matchings in a graph) has exponential extension complexity. This paper builds upon that foundation to address a more nuanced question: If we cannot represent the matching polytope exactly with a small LP, can we at least approximate it efficiently?

The Limits of Approximation

A Fully-Polynomial Size Relaxation Scheme (FPSRS) is the polyhedral analogue of an FPTAS. It is a family of LPs that approximate a polytope within a factor of $(1 + \epsilon)$, where the number of constraints grows polynomially in both the problem size $n$ and the inverse of the error $1/\epsilon$.

It was already known that for any constant $\rho > 1$, one can construct a $\rho$-approximation of the matching polytope using a polynomial number of constraints (specifically by considering odd-set constraints of bounded size). However, this research demonstrates a hard limit to this approach. The authors prove that as soon as the desired approximation factor reaches $(1 + \epsilon/n)$, the required size of the LP jumps from polynomial to exponential ($2^{\Omega(n)}$).

Methodology: From Combinatorics to Information Theory

The original proof of exponential extension complexity for matching relied on the "rectangle corruption bound." In contrast, this work employs an information-theoretic framework to analyze the slack matrix of the polytope.

Slack Matrices and Nonnegative Rank

Yannakakis’s Theorem establishes that the extension complexity of a polytope is equal to the nonnegative rank of its slack matrix—a matrix where each entry represents the "slack" or distance between a vertex and a constraint. To prove a lower bound on the size of an LP, one must prove a lower bound on the nonnegative rank of this matrix.

Wyner’s Common Information

The authors utilize Wyner’s common information, a concept from information theory introduced by Braun and Pokutta. By treating the slack matrix as a joint probability distribution between row and column indices, they ask: how much "seed" information is required for two independent parties to generate these indices? They show that the common information provides a lower bound on the logarithm of the nonnegative rank, allowing them to analyze perturbations of slack matrices effectively.

The Direct Sum Structure

The core of the proof lies in identifying a "direct sum structure" within the matching problem. By partitioning a large graph into many small, independent subgraphs (or "chunks"), the authors demonstrate that the total complexity of the system is essentially the sum of the complexities of these individual parts. This additive property in the information-theoretic domain translates to a multiplicative (and thus exponential) growth in the total number of required constraints.

Key Insights

  1. Sharp Separation: The result provides a sharp boundary. While constant-factor approximations are "easy" for LPs, high-precision approximations (specifically those scaling with $1/n$) are "hard."
  2. P vs. Polyhedral Complexity: The paper reinforces the decoupling of algorithmic efficiency and polyhedral size. A problem can be easy to solve (like matching) but impossible to describe concisely via linear inequalities, even when allowing for small errors.
  3. Shared Hardness Source: The research reveals that the matching polytope's hardness stems from the same structural properties as the Correlation Polytope (associated with the NP-hard Clique problem). Both exhibit a direct sum structure that resists compression into small LPs.

Conclusion and Future Directions

This work establishes that matching is the first problem in P that does not admit an FPSRS. While this settles the question for Linear Programming, the frontier remains open for Semidefinite Programming (SDP). SDPs are more powerful than LPs, and while exponential bounds exist for SDP representations of NP-hard problems like the Traveling Salesperson Problem, it is not yet known if the matching polytope admits a polynomial-sized SDP relaxation scheme for high-precision approximations. The information-theoretic tools developed here provide a robust framework for exploring these questions in other areas of combinatorial optimization.

Summary updated

Abstract

The groundbreaking work of Rothvo{\ss} [arxiv:1311.2369] established that every linear program expressing the matching polytope has an exponential number of inequalities (formally, the matching polytope has exponential extension complexity). We generalize this result by deriving strong bounds on the polyhedral inapproximability of the matching polytope: for fixed $0 < \varepsilon < 1$, every polyhedral $(1 + \varepsilon / n)$-approximation requires an exponential number of inequalities, where $n$ is the number of vertices. This is sharp given the well-known $\rho$-approximation of size $O(\binom{n}{\rho/(\rho-1)})$ provided by the odd-sets of size up to $\rho/(\rho-1)$. Thus matching is the first problem in $P$, whose natural linear encoding does not admit a fully polynomial-size relaxation scheme (the polyhedral equivalent of an FPTAS), which provides a sharp separation from the polynomial-size relaxation scheme obtained e.g., via constant-sized odd-sets mentioned above. Our approach reuses ideas from Rothvo{\ss} [arxiv:1311.2369], however the main lower bounding technique is different. While the original proof is based on the hyperplane separation bound (also called the rectangle corruption bound), we employ the information-theoretic notion of common information as introduced in Braun and Pokutta [http://eccc.hpi-web.de/report/2013/056/], which allows to analyze perturbations of slack matrices. It turns out that the high extension complexity for the matching polytope stem from the same source of hardness as for the correlation polytope: a direct sum structure.
BibTeX
@inproceedings{braun2015matching,
  author = {Gábor Braun and Sebastian Pokutta},
  title = {{The matching polytope does not admit fully-polynomial size relaxation schemes}},
  booktitle = {SODA},
  year = {2015},
  doi = {10.1137/1.9781611973730.57},
}
Figure