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 non-approximability 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 (2011) 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.
Introduction
Graph partitioning is a cornerstone of computer science, appearing in applications ranging from VLSI layout design to image segmentation and community detection. Two primary variants are the Balanced Separator problem, which seeks to divide a graph into two roughly equal pieces with minimal edge cuts, and the Uniform Sparsest Cut problem, which minimizes the ratio of edges cut to pairs of vertices separated.
Despite decades of study, a significant gap exists in our understanding of these problems. Current algorithms provide an $O(\sqrt{\log n})$ approximation, yet it remains unknown if they are APX-hard. This research investigates whether the Lasserre hierarchy—the most powerful known framework for convex relaxations—can provide a Polynomial Time Approximation Scheme (PTAS) for these problems.
The Lasserre Hierarchy and Global Constraints
To improve approximations, researchers employ hierarchies of Semidefinite Programs (SDPs). The Lasserre hierarchy is considered the "gold standard," capturing high-order correlations between variables. However, handling "global" constraints, such as the balance requirement in graph partitioning, is notoriously difficult in this framework.
The authors provide a new, simplified observation for "lifting" polynomial constraints to higher levels of the hierarchy. This technical contribution makes it easier to prove that constructed vectors satisfy the necessary global balance constraints within the Lasserre framework.
Constructing the Integrality Gap
The core of this work is an integrality gap construction. The authors build specific synthetic graphs where the Lasserre SDP relaxation yields a solution significantly smaller than the actual optimal cut.
The construction begins with a hard instance of the 3-XOR problem, known to have a large Lasserre gap. This instance is transformed into a graph partitioning problem using specialized gadgets—subgraphs that translate XOR logic into the geometry of graph cuts. These gadgets are then combined with expander graphs to ensure the resulting instance is robust.
Key Results
The study demonstrates that the Lasserre hierarchy is not a "silver bullet" for graph partitioning:
- Constant Factor Gaps: For both Balanced Separator and Uniform Sparsest Cut, the ratio between the true optimal cut and the Lasserre SDP value is at least $(1 + \epsilon)$ for some constant $\epsilon > 0$. For specific parameters, this ratio is at least 1.007.
- Linear Rounds: Unlike many lower bounds that only apply to a small number of rounds, this gap persists even for a linear number of rounds ($\Omega(n)$).
- Constant Degree Graphs: The construction can be modified to produce constant-degree graphs, making the results applicable to a broader range of graph classes.
Conclusion
While the proven gap of 1.007 is small, it is sufficient to rule out a PTAS via the Lasserre hierarchy. This work highlights the limitations of even the most powerful SDP relaxations in grasping the global connectivity required for perfect graph partitioning. Future work may apply these "lifting" techniques to other resource-constrained problems like Knapsack, or seek to bridge the gap between these results and the larger gaps predicted by the Unique Games Conjecture.
Summary updated