  Compression and sparsification algorithms are frequently applied in a
preprocessing step before analyzing or optimizing large networks/graphs. In
this paper we propose and study a new framework contracting edges of a graph
(merging vertices into super-vertices) with the goal of preserving pairwise
distances as accurately as possible. Formally, given an edge-weighted graph,
the contraction should guarantee that for any two vertices at distance $d$, the
corresponding super-vertices remain at distance at least $\varphi(d)$ in the
contracted graph, where $\varphi$ is a tolerance function bounding the
permitted distance distortion. We present a comprehensive picture of the
algorithmic complexity of the contraction problem for affine tolerance
functions $\varphi(x)=x/\alpha-\beta$, where $\alpha\geq 1$ and $\beta\geq 0$
are arbitrary real-valued parameters. Specifically, we present polynomial-time
algorithms for trees as well as hardness and inapproximability results for
different graph classes, precisely separating easy and hard cases. Further we
analyze the asymptotic behavior of contractions, and find efficient algorithms
to compute (non-optimal) contractions despite our hardness results.
