TY - GEN

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

AU - Dinitz, Michael

AU - Kortsarz, Guy

AU - Raz, Ran

PY - 2012/12/1

Y1 - 2012/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 [ICALP 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 non-trivial 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 Ω(logn)/k from [17]. Our main technique is subsampling the edges of 2-query 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 [ICALP 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 non-trivial 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 Ω(logn)/k from [17]. Our main technique is subsampling the edges of 2-query 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.

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

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

U2 - 10.1007/978-3-642-31594-7_25

DO - 10.1007/978-3-642-31594-7_25

M3 - Conference contribution

AN - SCOPUS:84871998589

SN - 9783642315930

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 290

EP - 301

BT - Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Proceedings

T2 - 39th International Colloquium on Automata, Languages, and Programming, ICALP 2012

Y2 - 9 July 2012 through 13 July 2012

ER -