Label cover instances with large girth and the hardness of approximating basic k-Spanner

Michael Dinitz, Guy Kortsarz, Ran Raz

Research output: Contribution to journalArticlepeer-review

16 Scopus citations


We study the well-known Label Cover problem under the additional requirement that problem instances have large girth. We show that if the girth is some k, the problem is roughly 2(log1-∈ n)/k hard to approximate for all constant ∈ > 0. A similar theorem was claimed by Elkin and Peleg [2000] as part of an attempt to prove hardness for the basic k-spanner problem, but their proof was later found to have a fundamental error. Thus, we give both the first nontrivial lower bound for the problem of Label Cover with large girth as well as the first full proof of strong hardness for the basic k-spanner problem, which is both the simplest problem in graph spanners and one of the few for which super-logarithmic hardness was not known. Assuming NP ⊈ BPTIME(2polylog(n)), we show (roughly) that for every k ≥ 3 and every constant ∈ > 0, it is hard to approximate the basic k-spanner problem within a factor better than 2(log1-∈ n)/k. This improves over the previous best lower bound of only Ω(log n)/k from Kortsarz [2001]. Our main technique is subsampling the edges of 2-query probabilistically checkable proofs (PCPs), which allows us to reduce the degree of a PCP to be essentially equal to the soundness desired. This turns out to be enough to basically guarantee large girth.

Original languageEnglish (US)
Article number25
JournalACM Transactions on Algorithms
Issue number2
StatePublished - Dec 1 2015
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Mathematics (miscellaneous)


  • Graph spanners
  • Probabilistically checkable proofs


Dive into the research topics of 'Label cover instances with large girth and the hardness of approximating basic k-Spanner'. Together they form a unique fingerprint.

Cite this