Vi studerar det välkända problemet med Label Cover under det ytterligare kravet att problemfall har stor omkrets. Vi visar att om omkretsen är någon k, problemet är ungefär 2 (log 1− n) / k svårt att approximera för alla konstant > 0. Ett liknande teorem påstods av Elkin och Peleg [2000] som en del av ett försök att bevisa hårdhet för det grundläggande k-spannerproblemet, men deras bevis visade sig senare ha ett grundläggande fel. Således ger vi både den första icke-trivial lägre gränsen för problemet med Label Cover med stor omkrets samt det första fullständiga beviset på stark hårdhet för den grundläggande k-spanner problem, vilket är både det enklaste problemet i graf skiftnycklar och en av de få för vilka super-logaritmisk hårdhet inte var känd. Om man antar att N P BPTIME (2 polylog(n) ), visar vi (i stort sett) att för varje k ≥ 3 och varje konstant > 0, är det svårt att uppskatta den grundläggande k-spanner problem inom en faktor bättre än 2 (log 1− n) / k. Detta förbättrar över den tidigare bästa nedre gränsen av endast (log n)/k från Kortsarz [2001]. Vår huvudsakliga teknik är subsampling kanterna av 2-query probabilistically kontrollerbara bevis (PCPs), vilket gör att vi kan minska graden av en PCP att vara i huvudsak lika med den ljudstyrka som önskas. Detta visar sig vara tillräckligt för att i princip garantera stor omkrets.
På hårdhetssidan har det visat sig att det för alla konstanta  till > 0 och för 3 ≤ k ≤ log 1‐2 till n, om inte N P -BP T IM E(2 poly log n ), finns det ingen polynom-tid algoritm som approximerar den grundläggande k-spanner problem till en faktor som är bättre än 2 (log 1- på n) / k REF.
Label Cover Instances with Large Girth and the Hardness of Approximating Basic k-Spanner
{'venue': 'TALG', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}