TL;DR
This paper demonstrates that even the most powerful "lift-and-project" optimization techniques—specifically the Lasserre hierarchy—fail to significantly improve our ability to approximate graph spanners. By proving large polynomial integrality gaps, the authors show that these sophisticated convex relaxations remain far from the true optimal solutions for directed spanners, undirected spanners, and related Steiner network problems.
What Problem Does This Paper Address?
A graph spanner is a subgraph that preserves distances between nodes within a certain multiplicative factor, known as "stretch." For example, in a 3-spanner, the distance between any two nodes is at most three times the distance in the original graph. Finding the smallest possible spanner for a given graph is a fundamental problem in network design, with applications in routing, distributed computing, and biology.
Most existing approximation algorithms for finding optimal spanners rely on Linear Programming (LP) relaxations. While we know the "basic" LPs have limitations (expressed as integrality gaps), researchers hoped that more powerful hierarchies of relaxations, like the Lasserre hierarchy, could break through current approximation barriers. The Lasserre hierarchy is a sequence of increasingly complex Semidefinite Programming (SDP) relaxations that eventually converge to the true optimal solution, but solving higher levels becomes computationally expensive. This paper asks: Does even a high level of the Lasserre hierarchy provide a significantly better approximation for spanners?
Methods
The authors establish their results by constructing "hard" instances of spanner problems where the Lasserre relaxation suggests a very "cheap" solution exists, while the true optimal integral solution is actually very "expensive."
Key technical steps include:
- Projection Games: They start with a known integrality gap for "Projection Games" (a variant of the Label Cover problem).
- Gap Amplification: They transform these Projection Game instances into complex graph structures. For the directed case, they use a "label-extended" graph with specific "outer edges" and "connection paths."
- Matrix Decomposition: The most difficult technical challenge was proving feasibility. To show a solution is valid for the Lasserre hierarchy, one must prove that certain "slack moment matrices" are Positive Semidefinite (PSD). The authors achieved this by carefully decomposing these large matrices into sums of simpler PSD matrices.
- Girth Pruning: For undirected graphs, they introduced a "subsampling and pruning" step to remove short cycles, ensuring that the only way to span certain edges is through the intended long paths.
Datasets
As a theoretical work, this paper does not use empirical datasets. Instead, it uses mathematical constructions of hard problem instances. These instances are built using:
- Randomly generated Projection Games as a base.
- Synthetic graph topologies designed to "trick" the LP/SDP into buying fractional edges that don't actually form valid paths in an integral solution.
Key Insights and Ideas
- Lasserre is not a Silver Bullet: Despite being significantly stronger than other hierarchies (like Sherali-Adams or Lovász-Schrijver), Lasserre still suffers from polynomial gaps for spanner problems. This suggests that the difficulty of these problems is inherent to the combinatorial structure, not just a weakness of standard LPs.
- Tracking the "Generic" Bound: For undirected spanners, the gap found by the authors "tracks" the known universal upper bounds. This implies that current "generic" greedy algorithms might be close to the best possible performance achievable through these mathematical frameworks.
- Consistency over Connectivity: The proof relies heavily on the "consistency" properties of the fractional solution—the idea that the hierarchy can be "fooled" into thinking a consistent label assignment exists across the graph when it actually doesn't.
Key Results
The paper proves polynomial integrality gaps for $n^{\Omega(\epsilon)}$ levels of the Lasserre hierarchy (where $n$ is the number of vertices):
- Directed $(2k-1)$-Spanner: An integrality gap of approximately $(n/k)^{1/18}$.
- Basic (Undirected) $(2k-1)$-Spanner: An integrality gap of $n^{\Theta(1/k)}$.
- Steiner Networks: The authors extended these results to Directed Steiner Network (DSN) and Shallow-Light Steiner Network (SLSN), proving gaps of at least $n^{1/16}$.
These results show that even with massive computational effort (polynomial levels of the hierarchy), the relaxation's estimate can be off by a factor that grows significantly with the size of the graph.
Limitations and Future Work
- Constant Exponents: The specific constants in the exponents (like $1/18$ or $1/16$) are likely not tight. Future work could aim to sharpen these bounds to match known hardness results more closely.
- Beyond Hierarchies: Since hierarchies fail to close the gap, this work motivates the search for entirely different algorithmic approaches or perhaps even stronger proof techniques to establish the absolute computational hardness of these problems.
- Undirected Complexity: The undirected case required much more complex "girth" arguments; simplifying these constructions while maintaining the gap remains an open challenge.
Summary updated