Parameters of two-prover-one-round game and the hardness of connectivity problems

DOI10.1137/1.9781611973402.118MaRDI QIDQ5384080zbMATH OpenOpenAlexFDO

Authors B. Laekhanukit

Publication date 20 June 2019

Published in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1212.0752

Mathematics Subject Classification ID

Connectivity (05C40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Abstract: 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^{s}igma$, for some (very) small constant $sigma>0$, to hardness results of the form $k^c$ 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 $D^{c^{\prime }}$, where $D$ is the number of demand pairs (or the number of terminals). Thus, we give improved hardness results of k^{1/2-epsilon} and k^{1/10-epsilon} for the root $k$-connectivity problem on directed and undirected graphs, k^{1/6-epsilon} for the vertex-connectivity survivable network design problem on undirected graphs, and k^{1/6-epsilon} for the vertex-connectivity $k$-route cut problem on undirected graphs.

Recommendations

• A two-prover one-round game with strong soundness
• scientific article; zbMATH DE number 1947057
• Parallel repetition of two-prover one-round games: an exposition
• Hardness of Approximation for Vertex-Connectivity Network Design Problems
• Approximation algorithms and hardness of the \(k\)-route cut problem

Cited in

(16)

• Improved approximation algorithms for minimum cost node-connectivity augmentation problems
• A note on degree vs gap of Min-Rep label cover and improved inapproximability for connectivity problems
• Improved approximation algorithms for \(k\)-connected \(m\)-dominating set problems
• On rooted \(k\)-connectivity problems in quasi-bipartite digraphs
• An improved approximation algorithm for the minimum cost subset \(k\)-connected subgraph problem
• Approximating source location and star survivable network problems
• scientific article; zbMATH DE number 7651209 (Why is no real title available?)
• $O(\log^2{k}/\log\log{k})$-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial Time Algorithm
• Parameterized inapproximability of independent set in \(H\)-free graphs
• Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs
• On rooted \(k\)-connectivity problems in quasi-bipartite digraphs
• The parameterized complexity of the survivable network design problem
• Tree-like distance colouring for planar graphs of sufficient girth
• Hardness of approximating bounded-degree max 2-CSP and independent set on k-claw-free graphs
• A new approach for approximating directed rooted networks
• Survivable network design with group-to-group requirement

This page was built for publication: Parameters of two-prover-one-round game and the hardness of connectivity problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5384080)