Lift & Project Systems Performing on the Partial-Vertex-Cover Polytope

Konstantinos Georgiou, Edward Lee

TL;DR

This paper investigates the limits of "Lift & Project" (L&P) hierarchies—automated systems used to strengthen mathematical relaxations—when applied to the $t$-Partial Vertex Cover ($t$-PVC) problem. The authors prove that even highly sophisticated L&P systems (like Sherali-Adams and Lovász-Schrijver) fail to provide tight approximations, maintaining a massive "integrality gap" even after many rounds of refinement.

What Problem Does This Paper Address?

In the classic Vertex Cover problem, you want to find the smallest set of vertices that touches every edge in a graph. The $t$-Partial Vertex Cover ($t$-PVC) is a more flexible variant: you only need to cover at least $t$ edges. While $t$-PVC has a simple 2-approximation algorithm, researchers often look to Lift & Project (L&P) hierarchies to find even better solutions.

L&P hierarchies (like Sherali-Adams, Lovász-Schrijver, and Lasserre) are "meta-algorithms." They take a simple Linear Program (LP) and systematically add new constraints to make it "stronger" (closer to the true integer solution). The "Integrality Gap" (IG) measures the failure of these relaxations: it’s the ratio between the true optimal integer solution and the "fake" fractional solution the LP finds. A high IG means the math is "fooled" into thinking a much cheaper solution exists than is actually possible.

The authors ask: Do these powerful hierarchies actually help us solve $t$-PVC better, or do they get stuck?

Methods

The authors employ a mix of probabilistic construction and spectral analysis:

  • Bad Instances: They primarily analyze the unweighted clique ($K_n$) and the star graph. These simple structures are surprisingly effective at "fooling" complex hierarchies.
  • Global Distributions: To prove a lower bound for the Sherali-Adams (SA) hierarchy, they define a "Random Process." They pick vertices independently at random with a very small probability $p$. This creates a "global distribution" of solutions that satisfies the hierarchy's local consistency requirements but results in a very low fractional cost.
  • Spectral Analysis for Lasserre: For the Lasserre hierarchy (the strongest known system), they analyze the eigenvalues of "slack matrices" to show that the system cannot rule out certain cheap, non-existent solutions.

Datasets

As a theoretical computer science paper, it does not use empirical datasets. Instead, it uses graph families as benchmarks:

  • Complete Graphs (Cliques): Used to show the failure of SA and Lasserre hierarchies.
  • Star Graphs: Used to demonstrate a "rare phenomenon" where a weak Level-1 LP actually outperforms a more complex Semidefinite Program (SDP) used in previous state-of-the-art algorithms.

Key Insights and Ideas

  • The "Hierarchy Failure": Usually, we expect that adding "levels" to a hierarchy (more constraints) will quickly shrink the integrality gap. For $t$-PVC, the authors show that for many systems, the gap remains as large as $\approx n/t$ even at level-$\Theta(n)$. This is nearly as bad as it can get.
  • LP vs. SDP Paradox: In a surprising twist, the authors show that a very simple Level-1 Sherali-Adams LP can solve the star graph perfectly, whereas a much more complex SDP (which provided the best-known approximation ratio for $t$-PVC) is completely fooled by it. This highlights that "stronger" hierarchies aren't always better for every specific instance.
  • Lasserre’s Resilience: The Lasserre hierarchy is often considered the "final boss" of L&P systems. While it performs better than SA, the authors still found a superconstant integrality gap at linear levels, proving that even the most powerful automated tools have blind spots for $t$-PVC.

Key Results

  • Sherali-Adams/LS+: For any $\epsilon > 0$, level-$\Theta(n)$ relaxations have an integrality gap of at least $(1 - \epsilon)n/t$. This means the hierarchy thinks the solution is $n/t$ times cheaper than it actually is.
  • Lasserre Level-1: Proved an integrality gap of $O(\sqrt{n})$.
  • Lasserre General: Established a superconstant integrality gap for all level-$\Theta(n)$ Lasserre-derived SDPs.
  • Tightness: The authors note their lower bounds are nearly tight, as level-$n$ relaxations (the maximum possible) always yield a gap of 1 (the perfect solution).

Limitations and Future Work

  • Parameter Range: The strongest results (the $n/t$ gaps) are most significant when $t$ is small relative to $n$ (specifically $t = O(n)$). The behavior of these hierarchies when $t$ is very close to the total number of edges $|E|$ (approaching the standard Vertex Cover) remains an area for further refinement.
  • The "Gap 2" Quest: A major open question in this field is whether $t$-PVC admits a polysize LP or SDP relaxation with an integrality gap of exactly 2. This paper shows that many standard "recipes" for building such relaxations will fail to reach that goal.
  • Search for New Hierarchies: Since standard L&P systems fail, the work suggests we might need problem-specific constraints rather than "off-the-shelf" hierarchies to make progress on $t$-PVC.

Summary updated

BibTeX
@article{georgiou2020lift,
  author = {Konstantinos Georgiou and Edward Lee},
  title = {{Lift \& Project Systems Performing on the Partial-Vertex-Cover Polytope}},
  journal = {Theoretical Computer Science},
  year = {2020},
  doi = {10.1016/j.tcs.2020.03.004},
}
Figure