2012/12/04 by Bundit Laekhanukit, Laekhanukit, Bundit · 1 citation
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #G.2.2 #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1212.0752
openalex publication_date 2012/12/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Optimizing parameters of Two-Prover-One-Round Game (2P1R) is an important task in PCPs literature as it would imply a smaller PCP with the same or stronger soundness. While this is a basic question in PCPs community, the connection between the parameters of PCPs and hardness of approximations is sometime obscure to approximation algorithm community. In this paper, we investigate the connection between the parameters of 2P1R and the hardness of approximating the class of so-called connectivity problems, which includes as subclasses the survivable network design and (multi)cut problems. Based on recent development on 2P1R by Chan (ECCC 2011) and several techniques in PCPs literature, we improve hardness results of some connectivity problems that are in the form kσ, for some (very) small constant σ>0, to hardness results of the form kc for some explicit constant c, where k is a connectivity parameter. In addition, we show how to convert these hardness into hardness results of the form Dc', where D is the number of demand pairs (or the number of terminals). Thus, we give improved hardness results of k1/2-ε and k1/10-ε for the root k-connectivity problem on directed and undirected graphs, k1/6-ε for the vertex-connectivity survivable network design problem on undirected graphs, and k1/6-ε for the vertex-connectivity k-route cut problem on undirected graphs.