Distance-preserving graph contractions

Aaron Bernstein, Karl Däubel, Yann Disser, Max Klimm, Torsten Mütze, Frieder Smolny

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

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 supervertices) 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 supervertices remain at distance at least ϕ(d) in the contracted graph, where ϕ 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 ϕ(x) = x/α − β, where α ≥ 1 and β ≥ 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 (nonoptimal) contractions despite our hardness results.

Original languageEnglish (US)
Pages (from-to)1607-1636
Number of pages30
JournalSIAM Journal on Discrete Mathematics
Volume33
Issue number3
DOIs
StatePublished - 2019
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Keywords

  • Contraction
  • Distance oracle
  • Graph compression
  • Spanner

Fingerprint Dive into the research topics of 'Distance-preserving graph contractions<sup>∗</sup>'. Together they form a unique fingerprint.

Cite this