Abstract
This paper establishes a new, super-logarithmic hardness of approximation for the basic $k$-spanner problem, proving it is difficult to solve within a factor of $2^{(\log^{1-\epsilon} n)/k}$. By introducing a novel technique of random edge subsampling in Probabilistically Checkable Proofs (PCPs), the authors resolve a decade-old discrepancy in the literature. This method allows for the construction of Label Cover instances that maintain large girth without sacrificing the hardness of the underlying gap, effectively bridging the gap between theoretical lower bounds and known approximation algorithms.
Introduction
In the field of network design, the $k$-spanner problem is a fundamental optimization challenge. Given a graph $G$, a $k$-spanner is a subgraph $G'$ such that for every pair of vertices, the distance in $G'$ is at most $k$ times the distance in $G$. The objective is to find the sparsest possible $k$-spanner (i.e., the one with the fewest edges).
While the case for $k=2$ is well-understood, the problem becomes significantly more complex for $k \geq 3$. In 2000, Elkin and Peleg proposed a high hardness result for the $k$-spanner problem. However, their proof contained a fundamental flaw: the construction required the underlying Label Cover instances to have large girth (the absence of short cycles). Standard techniques to increase the hardness of these instances, such as parallel repetition, inherently create many short cycles, thereby destroying the large-girth property. This paper fixes this long-standing error and provides a rigorous proof for the hardness of the $k$-spanner problem.
The Challenge: Girth vs. Hardness
The primary obstacle in proving $k$-spanner hardness lies in the structure of the Label Cover problem. Label Cover is a standard starting point for many hardness-of-approximation proofs. To prove that $k$-spanner is hard, one must reduce a Label Cover instance to a $k$-spanner instance. For this reduction to be valid, the Label Cover graph must have a girth greater than $k$.
Historically, researchers faced a "Sparsity Paradox." To make a problem mathematically "harder" to approximate, one typically uses parallel repetition, which increases the complexity of the constraints but also increases the density of short cycles (specifically cycles of length 4). Previous attempts to fix the girth after repetition usually resulted in a loss of the hardness "gap," making the resulting proof invalid for high hardness factors.
Methods: Random Subsampling and the Sampling Lemma
The authors introduce a clever "subsampling" strategy that reverses the traditional order of operations to maintain both hardness and large girth.
- Parallel Repetition First: The process begins by applying parallel repetition to a standard Label Cover instance derived from Max-3SAT(5). This creates a highly "hard" instance, albeit one with a girth of only 4.
- Random Subsampling: Instead of manual graph surgery, the authors randomly delete edges from the graph. While deleting edges usually makes an optimization problem easier, the authors prove a Sampling Lemma: by carefully calibrating the sampling probability, one can eliminate almost all short cycles while preserving the integrity of the hardness gap.
- Deterministic Cleanup: After subsampling has removed the vast majority of short cycles, the few remaining ones are removed manually. Because the graph is already extremely sparse, this final cleanup does not significantly impact the graph's mathematical properties.
- Reduction: The resulting large-girth, high-hardness Label Cover instance is then transformed into a $k$-spanner instance using established reduction techniques.
Key Insights
The Importance of Supergirth
A critical distinction made in the paper is between the girth of the full graph and the "supergirth"—the girth of the underlying constraint graph. The authors demonstrate that for the $k$-spanner problem, the supergirth is the primary driver of hardness. By controlling the supergirth through subsampling, they can ensure the reduction to $k$-spanner remains robust.
Order of Operations
The "aha moment" of this research is the realization that the order of operations in previous attempts was backwards. By sparsifying the graph after the hardness has been boosted via parallel repetition, the authors can maintain the necessary error rates (soundness) while achieving the structural requirements (girth) needed for the $k$-spanner reduction.
Results and Implications
The paper provides the first non-trivial, super-logarithmic lower bound for the basic $k$-spanner problem. Specifically, it proves that Label Cover with girth $> k$ is hard to approximate within a factor of $2^{(\log^{1-\epsilon} n)/k}$, assuming $NP \not\subseteq BPTIME(2^{polylog(n)})$.
This result is nearly tight. For various values of $k$, the hardness factor matches the best-known approximation algorithms. This suggests that the $2^{(\log^{1-\epsilon} n)/k}$ threshold represents a fundamental limit in our ability to efficiently approximate sparse backbones in networks.
Conclusion and Future Work
This work settles a decade-old question regarding the complexity of $k$-spanners, but it opens new avenues in complexity theory. The authors note that the complexity of the Min-Rep problem (a Label Cover variant) remains an open question when the supergirth is small but the expanded graph's girth is large. Additionally, the authors suggest that exploring these techniques within the framework of the Unique Games Conjecture (UGC) could lead to further breakthroughs, though they suspect the hardness results for "Unique" Label Cover with large girth may be lower than those established here.
Summary updated