Strong reductions for extended formulations

Gábor Braun, Sebastian Pokutta, Aurko Roy

Abstract

This research significantly expands the theoretical framework for proving lower bounds on the size of Linear Programs (LPs) and Semidefinite Programs (SDPs) required to solve combinatorial optimization problems. By introducing "non-affine" reductions and a novel framework for fractional optimization, the authors establish powerful new lower bounds for classic problems including MaxCut, SparsestCut, and Matching on 3-regular graphs. These results demonstrate that even with sophisticated relaxation techniques, many fundamental problems remain intractable for small extended formulations.

Introduction

In combinatorial optimization, a common strategy for solving NP-hard problems is to "relax" them into LPs or SDPs. The efficiency of these relaxations is measured by their extended formulation size—the number of constraints needed to represent the problem. A central goal in theoretical computer science is to prove that for certain problems, any LP or SDP formulation must be exponentially large relative to the input size, effectively rendering them "LP-hard" or "SDP-hard."

Historically, the primary tool for proving these lower bounds was a reduction mechanism requiring an "affine" (linear) relationship between problems. This requirement acted as a significant bottleneck, making it difficult to prove hardness for problems with complex relationships, such as VertexCover, or fractional problems like SparsestCut, where the objective is a ratio. This work breaks these rigidity constraints to provide a more flexible and powerful reduction framework.

Methodological Innovations

The authors introduce three major theoretical extensions to the existing reduction framework:

  1. Reductions with "Computation": Instead of a simple linear map, the authors allow reductions to involve "extra computation" in the form of additional LP or SDP constraints. As long as this intermediate mapping has a small formulation, it can be used to prove hardness for the target problem, enabling the analysis of non-affine relations.
  2. Fractional LP/SDP Framework: The paper develops a formal method to analyze the complexity of fractional optimization problems where the objective is a ratio (e.g., capacity divided by demand). Because these ratios do not reside in a low-dimensional linear space, standard frameworks often fail. The new framework models how solvers typically handle these ratios by optimizing the numerator and denominator simultaneously.
  3. Slack Matrix Factorization: Building upon Yannakakis’s Factorization Theorem, the authors relate the size of an LP/SDP to the "rank" of a specific matrix called the slack matrix. They prove that their new reduction types preserve or predictably transform these ranks, allowing for rigorous lower-bound proofs.

Key Hardness Results

The paper provides a comprehensive "table of hardness" for several major optimization problems, establishing new benchmarks for inapproximability within the LP and SDP paradigms.

Table 1: Summary of new hardness results for various optimization problems, including inapproximability factors and the paradigms (LP/SDP) used.

Key findings summarized in the table include:

  • Matching on 3-regular graphs: The authors prove there is no polynomial-sized LP formulation for this problem, settling a long-standing open question for this restricted graph class.
  • MaxCut: The work establishes the first explicit SDP-hardness for an inapproximability factor of $15/16 + \epsilon$.
  • SparsestCut: The problem is proven LP-hard (factor $2 - \epsilon$) and SDP-hard (factor $16/15 - \epsilon$), even when the supply graph has bounded treewidth.
  • IndependentSet: The authors demonstrate a massive Lasserre integrality gap of $n^{1-\gamma}$ after $O(n^\gamma)$ rounds, showing that the Lasserre hierarchy—often considered the "gold standard" for SDP relaxations—can be strictly suboptimal compared to other approximations.

Theoretical Insights and Implications

  • The Power of Non-Affinity: By allowing reductions to be LPs themselves, the authors show that "gap amplification" and "boosting" (standard techniques in complexity theory) can finally be applied to the study of extended formulations.
  • Treewidth Limits: The results show that even for graphs with simple structures (bounded treewidth), problems like SparsestCut remain hard for small LPs and SDPs. This provides an unconditional analogue to known NP-hardness results.
  • Lasserre is Not Always King: The proof of a new integrality gap for IndependentSet demonstrates that the Lasserre hierarchy does not always provide the tightest possible relaxation, challenging common assumptions in the field.

Limitations and Future Work

While these results represent a major step forward, several gaps remain. For MaxCut, the proven SDP-hardness factor of $15/16$ (~0.937) is still higher than the best known algorithmic approximation (Goemans-Williamson) of ~0.878. Additionally, results for problems like BalancedSeparator rely on the Unique Games Conjecture; their ultimate standing depends on the resolution of that conjecture. Finally, for the Matching problem, it remains an open challenge to find a family of bounded-degree graphs where the lower bound can be strengthened to a full $2^{\Omega(n)}$.

Summary updated

Abstract

We generalize the reduction mechanism for linear programming problems and semidefinite programming problems from Braun et al. (Inapproximability of combinatorial problems via small LPs and SDPs, 2015) in two ways (1) relaxing the requirement of affineness, and (2) extending to fractional optimization problems. As applications we provide several new LP-hardness and SDP-hardness results, e.g., for the problem, the problem, and the problem and show how to extend ad-hoc reductions between Sherali–Adams relaxations to reductions between LPs.
BibTeX
@article{braun2018strong,
  author = {Gábor Braun and Sebastian Pokutta and Aurko Roy},
  title = {{Strong reductions for extended formulations}},
  journal = {Math. Program.},
  year = {2018},
  doi = {10.1007/s10107-018-1316-y},
}
Figure