TY - JOUR

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

AU - Dinitz, Michael

AU - Kortsarz, Guy

AU - Raz, Ran

N1 - Publisher Copyright:
© 2015 ACM.

PY - 2015/12/1

Y1 - 2015/12/1

N2 - 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.

AB - 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.

KW - Graph spanners

KW - Probabilistically checkable proofs

UR - http://www.scopus.com/inward/record.url?scp=84954223441&partnerID=8YFLogxK

U2 - 10.1145/2818375

DO - 10.1145/2818375

M3 - ???researchoutput.researchoutputtypes.contributiontojournal.article???

AN - SCOPUS:84954223441

SN - 1549-6325

VL - 12

JO - ACM Transactions on Algorithms

JF - ACM Transactions on Algorithms

IS - 2

M1 - 25

ER -