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

Gábor Braun, Sebastian Pokutta

TL;DR

Even though the matching problem can be solved efficiently in polynomial time, it cannot be approximated arbitrarily well by a "small" linear program. This paper proves that any linear programming (LP) relaxation attempting to approximate the matching problem within a factor of $(1 - \epsilon/n)$ requires an exponential number of inequalities, ruling out the existence of a "fully-polynomial" size relaxation scheme.

What Problem Does This Paper Address?

In the world of optimization, we often distinguish between problems that are easy (in P) and those that are hard (NP-hard). Linear Programming (LP) is one of our most powerful tools for solving these problems. A natural question arises: which problems can be expressed as an LP with a manageable (polynomial) number of constraints? This is the study of extension complexity.

Surprisingly, some "easy" problems like the matching problem (finding the largest set of edges in a graph that don't share vertices) have been shown to have exponential extension complexity—meaning the exact "matching polytope" requires an astronomical number of constraints to describe.

The authors of this paper tackle the next logical question: If we can't describe the matching polytope exactly with a small LP, can we at least approximate it? Specifically, they look for a Fully-Polynomial Size Relaxation Scheme (FPSRS). This is the LP equivalent of an FPTAS (Fully Polynomial Time Approximation Scheme); it would be a family of LPs that get closer and closer to the true answer as you add more constraints, with the size growing polynomially relative to both the problem size ($n$) and the desired accuracy ($1/\epsilon$).

Methods

The authors move away from traditional combinatorial proofs and instead use an information-theoretic framework.

  1. Slack Matrices and Nonnegative Rank: The size of the smallest LP for a problem is known to be equal to the "nonnegative rank" of its slack matrix (a matrix representing the "gap" between constraints and vertices of a polytope).
  2. Common Information: To lower-bound this rank, the authors employ a concept from information theory called Wyner’s common information. They treat the slack matrix as a joint probability distribution and ask: how much "seed" information is needed to generate the row and column variables independently?
  3. Direct Sum Structure: They demonstrate that the matching problem possesses a "direct sum structure." By partitioning the graph into small, independent "chunks," they show that the total information (and thus the total complexity) must grow linearly with the number of chunks, leading to an overall exponential lower bound.
  4. Pinsker’s Inequality: They use this tool to relate the divergence of probability distributions to the total variation distance, allowing them to handle the "noise" introduced by approximation factors.

Datasets

As a theoretical computer science paper, this work does not use empirical datasets or benchmarks like ImageNet. Instead, the "data" consists of the mathematical structures of:

  • The Matching Polytope: The convex hull of all matchings in a complete graph $K_n$.
  • Slack Matrices: Specifically, the slack matrices associated with the matching polytope and its perturbations.

Key Insights and Ideas

  • P $\neq$ Small LP: The most profound insight is the continued decoupling of computational complexity (time) from polyhedral complexity (size). Matching is easy for an algorithm to solve, but "hard" for a linear program to describe, even approximately.
  • The $1/n$ Threshold: The paper identifies a sharp threshold. We already knew that constant-factor approximations (like a 0.9-approximation) can be done with polynomial-sized LPs. However, this paper shows that as soon as you try to get within a factor of $(1 - \epsilon/n)$, the required size jumps from polynomial to exponential.
  • Structural Hardness: The authors show that the matching problem is hard for LPs for the same underlying reason that the Correlation Polytope (associated with the NP-hard Clique problem) is hard: they both contain a specific "direct sum" of hard sub-structures.

Key Results

  • Exponential Lower Bound: For a fixed $0 < \epsilon < 1$, any LP that $(1 - \epsilon/n)$-approximates the matching problem on $n$ vertices requires $2^{\Omega(n)}$ inequalities.
  • No FPSRS: This result formally proves that the matching problem does not admit a fully-polynomial size linear programming relaxation scheme.
  • Sharp Separation: It provides a clear separation between problems that have a Polynomial Size Relaxation Scheme (PSRS) for constant $\epsilon$ and those that can be scaled to arbitrary precision (FPSRS).

Limitations and Future Work

  • Linear vs. Semidefinite: This paper focuses strictly on Linear Programming. While LPs are the most common tool, Semidefinite Programming (SDP) is a more powerful generalization. The authors note that while similar exponential bounds have been found for SDPs in other contexts (like the TSP), it remains an open question whether the matching problem has exponential semidefinite extension complexity in the approximate case.
  • Framework Versatility: The authors suggest that their information-theoretic approach is quite general. A promising future direction is applying this "common information" technique to prove inapproximability for other combinatorial problems that have resisted traditional proof methods.

Summary updated

Abstract

The groundbreaking work of Rothvoß [2014] 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 < ε < 1, every polyhedral (1 + ε/n)-approximation requires an exponential number of inequalities, where n is the number of vertices. This is sharp given the well-known ρ-approximation of size provided by the odd-sets of size up to ρ/(ρ — 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ß [2014], 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 [2013], which allows to analyze perturbations of slack matrices. It turns out that the high extension complexity for the matching polytope stems 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},
}

Loading related content...

Figure