Inapproximability of Additive Weak Contraction under SSEH and Strong UGC
share
Succinct representations of a graph have been objects of central study in computer science for decades. In this paper, we study the operation called Distance Preserving Graph Contractions, which was introduced by Bernstein et al. (ITCS, 2018). This operation gives a minor as a succinct representation of a graph that preserves all the distances of the original (up to some factor). The graph minor given from contractions can be seen as a dual of spanners as the distances can only shrink (while distances are stretched in the case of spanners). Bernstein et al. proved inapproximability results for the problems of finding maximum subset of edges that yields distance preserving graph contractions for almost major classes of graphs except for that of Additive Weak Contraction. The main result in this paper is filling the gap in the paper of Bernstein et al. We show that the Maximum Additive Weak Contraction problem on a graph with n vertices is inapproximable up to a factor of n^1-ϵ for every constant ϵ>0. Our hardness results follow from that of the Maximum Edge Biclique (MEB) problem whose inapproximability of n^1-ϵ has been recently shown by Manurangsi (ICALP, 2017) under the Small Set Expansion Hypothesis (SSEH) and by Bhangale et al. (APPROX, 2016) under the Strong Unique Games Conjecture (SUGC) (both results also assume NP⊈BPP).
READ FULL TEXT