Constant Factor Lasserre Integrality Gaps for Graph Partitioning Problems

Venkatesan Guruswami, Ali Kemal Sinop, Yuan Zhou

TL;DR

This paper shows that even the most powerful semidefinite programming (SDP) relaxations, known as the Lasserre hierarchy, cannot perfectly solve graph partitioning problems like Balanced Separator and Uniform Sparsest Cut. Specifically, they demonstrate that these relaxations have a "gap" – meaning the best solution found by the relaxation is provably worse than the true best solution, even for a linear number of relaxation levels. This is significant because it sets a fundamental limit on how well these SDPs can approximate these important problems.

What Problem Does This Paper Address?

Graph partitioning is a fundamental problem in computer science with applications ranging from circuit design to clustering. Two key variants are the Balanced Separator problem (finding a partition of graph vertices into two roughly equal sets that minimizes the number of edges between them) and the Uniform Sparsest Cut problem (minimizing the ratio of crossing edges to the product of the set sizes).

For these problems, there's a frustrating gap: we have approximation algorithms that can find solutions within a certain factor of the optimum, but we also know that finding the exact solution is computationally hard (NP-hard). However, for these specific problems, even proving APX-hardness (meaning no constant-factor approximation algorithm exists unless P=NP) is an open question.

The paper focuses on a powerful class of mathematical tools called Lasserre hierarchy relaxations. These are sophisticated semidefinite programs (SDPs) that can approximate integer optimization problems. While these relaxations are known to be very powerful, their limitations for graph partitioning problems were not well understood. The authors aim to understand these limitations by proving that even these advanced SDPs cannot achieve a perfect solution, thus establishing a fundamental barrier to achieving better approximation guarantees.

Methods

The core of the paper's contribution lies in constructing "gap instances." These are specific graph instances designed to expose the limitations of the Lasserre hierarchy. The authors leverage a known result by Schoenebeck on Lasserre gaps for the 3-XOR problem. They then build upon this by:

  • Gadget Reductions: They adapt techniques from previous work (specifically, [AMS11]) to reduce instances of the 3-XOR problem to instances of Balanced Separator and Uniform Sparsest Cut. This is like creating a "template" graph for the partitioning problem based on the structure of a 3-XOR problem.
  • Lifting Polynomial Constraints: A key technical contribution is a general observation that simplifies the process of "lifting" polynomial constraints (like the balance constraint in Balanced Separator) to higher levels of the Lasserre hierarchy. This makes their constructions more manageable.
  • Constructing Gap Instances: By combining the 3-XOR gap instances with carefully designed graph structures (including expander graphs and cliques), they construct specific graph instances for Balanced Separator and Uniform Sparsest Cut.
  • Analysis of SDP Solutions: They then analyze the solutions obtained by the Lasserre SDP relaxations on these constructed instances. They show that the SDP relaxation yields a "good" (though not necessarily optimal) solution.
  • Analysis of Integral Solutions: Crucially, they also prove that the true optimal integral solution for these constructed instances is provably worse than the SDP solution, establishing the integrality gap. They achieve this by leveraging pseudorandom structural properties of the random 3-XOR instances.
  • Constant Degree Modification: For practical purposes, they also show how to modify their gap instances to have a constant degree, which is a desirable property for graph algorithms.

Datasets

Not discussed in the paper. The paper focuses on theoretical constructions of specific graph instances rather than empirical evaluation on existing datasets.

Key Insights and Ideas

  • Fundamental Limits of Lasserre Hierarchy: The most significant insight is that even the most powerful known SDP relaxations (Lasserre hierarchy) have inherent limitations for fundamental graph partitioning problems. They cannot achieve a perfect approximation, even with a linear number of relaxation levels.
  • Bridging 3-XOR Gaps to Graph Partitioning: The paper elegantly demonstrates how to translate known integrality gaps from a simpler problem (3-XOR) to more complex graph partitioning problems, highlighting the interconnectedness of hardness results across different problem classes.
  • Simplifying Constraint Lifting: The authors provide a general technique for lifting polynomial constraints in the Lasserre hierarchy. This is a valuable methodological contribution that can simplify the construction of feasible solutions for future work involving these relaxations.
  • Constant Degree Gap Instances: The ability to construct gap instances with constant degrees is important. It shows that the observed gaps are not an artifact of complex graph structures with high degrees, making the results more robust.

Key Results

  • Constant Factor Integrality Gap for Balanced Separator: For the Balanced Separator problem, the paper proves that linear-round Lasserre SDP relaxations have an integrality gap bounded away from 1. Specifically, for a range of parameters, the optimal integral solution is at least $(1+\epsilon(\tau))$ times the SDP solution, where $\epsilon(\tau) > 0$.
  • Constant Factor Integrality Gap for Uniform Sparsest Cut: Similarly, for the Uniform Sparsest Cut problem, they show that linear-round Lasserre SDP relaxations have an integrality gap bounded away from 1, with the integral optimum being at least $(1+\epsilon)$ times the SDP solution for some constant $\epsilon > 0$.
  • Construction of Gap Instances: The paper provides explicit constructions of graph instances that demonstrate these integrality gaps. These instances are derived from random 3-XOR instances.
  • Constant Degree Gap Instances: The authors show that these gap instances can be constructed with constant degrees, which is a significant technical achievement.

Limitations and Future Work

  • APX-Hardness Remains Open: While the paper establishes limitations for Lasserre SDPs, it does not resolve the question of whether these problems are APX-hard. The authors' results show that SDPs cannot give a PTAS (Polynomial Time Approximation Scheme), but this is a weaker statement than APX-hardness.
  • Specific Parameter Ranges: The theorems for the integrality gaps are stated for specific ranges of parameters (e.g., $\tau$ for Balanced Separator) and for "large enough" constants $\beta$ and $M$. Further work might explore the behavior across all parameter ranges.
  • Future Work: The paper suggests that their techniques could be applied to other problems where Lasserre hierarchy relaxations are used. The observation on lifting polynomial constraints is a general tool that could be beneficial in other contexts. The authors also mention the potential for these results to inform the design of new approximation algorithms or to better understand the inherent hardness of these problems.

Summary updated

Abstract

Partitioning the vertices of a graph into two roughly equal parts while minimizing the number of edges crossing the cut is a fundamental problem (called balanced separator) that arises in many settings. For this problem, and variants such as the uniform sparsest cut problem where the goal is to minimize the fraction of pairs on opposite sides of the cut that are connected by an edge, there are large gaps between the known approximation algorithms and nonapproximability results. While no constant factor approximation algorithms are known, even APX-hardness is not known either. In this work we prove that for balanced separator and uniform sparsest cut, semidefinite programs from the Lasserre hierarchy (which are the most powerful relaxations studied in the literature) have an integrality gap bounded away from 1, even for $\Omega(n)$ levels of the hierarchy. This complements recent algorithmic results in Guruswami and Sinop [Proceedings of the 52nd Annual Symposium on Foundations of Computer Science (FOCS), 2011, pp. 482--491] which used the Lasserre hierarchy to give an approximation scheme for these problems (with runtime depending on the spectrum of the graph). Along the way, we make an observation that simplifies the task of lifting “polynomial constraints” (such as the global balance constraint in balanced separator) to higher levels of the Lasserre hierarchy.
BibTeX
@article{guruswami2014constant,
  author = {Venkatesan Guruswami and Ali Kemal Sinop and Yuan Zhou},
  title = {{Constant Factor Lasserre Integrality Gaps for Graph Partitioning Problems}},
  journal = {SIAM J. Optim.},
  year = {2014},
  url = {https://openreview.net/forum?id=ThsZYTTbmSg},
}
Figure