English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

Succinct representations of a graph have been objects of central study incomputer science for decades. In this paper, we study the operation called\emph{Distance Preserving Graph Contractions}, which was introduced byBernstein et al. (ITCS, 2018). This operation gives a minor as a succinctrepresentation of a graph that preserves all the distances of the original (upto some factor). The graph minor given from contractions can be seen as a dualof spanners as the distances can only shrink (while distances are stretched inthe case of spanners). Bernstein et al. proved inapproximability results forthe problems of finding maximum subset of edges that yields distance preservinggraph contractions for almost major classes of graphs except for that ofAdditive Weak Contraction.  The main result in this paper is filling the gap in the paper of Bernstein etal. We show that the Maximum Additive Weak Contraction problem on a graph with$n$ vertices is inapproximable up to a factor of $n^{1-\epsilon}$ for everyconstant $\epsilon>0$. Our hardness results follow from that of the MaximumEdge Biclique (\textsc{MEB}) problem whose inapproximability of$n^{1-\epsilon}$ has been recently shown by Manurangsi (ICALP, 2017) under the\textsc{Small Set Expansion Hypothesis (SSEH)} and by Bhangale et al. (APPROX,2016) under the \textsc{Strong Unique Games Conjecture (SUGC)} (both resultsalso assume $\mathrm{NP}\not\subseteq\mathrm{BPP}$).

Inapproximability of Additive Weak Contraction under SSEH and Strong UGC