2018/07/02 by Pasin Manurangsi, Manurangsi, Pasin
Computer Science · Engineering · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Packing Problems
paper · pdf · doi:10.48550/arxiv.1807.00936
openalex publication_date 2018/07/02 · openalex created_date 2022/08/04 · openalex updated_date 2026/07/28
This note concerns the trade-off between the degree of the constraint graph\nand the gap in hardness of approximating the Min-Rep variant of Label Cover\n(aka Projection Game). We make a very simple observation that, for NP-hardness\nwith gap g, the degree can be made as small as O(g \log g), which improves\nupon the previous \O(g1/2) bound from a work of Laekhanukit\n(SODA'14). Note that our bound is optimal up to a logarithmic factor since\nthere is a trivial \Δ-approximation for Min-Rep where \Δ is the\nmaximum degree of the constraint graph.\n Thanks to known reductions, this improvement implies better hardness of\napproximation results for Rooted k-Connectivity, Vertex-Connectivity\nSurvivable Network Design and Vertex-Connectivity k-Route Cut.\n