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

Michael Dinitz, Guy Kortsarz, Ran Raz

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…