Distance-preserving graph contractions

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations


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 ϕ(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 a ne 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 the size of contractions, and find efficient algorithms to compute (non-optimal) contractions despite our hardness results.

Original languageEnglish (US)
Title of host publication9th Innovations in Theoretical Computer Science, ITCS 2018
EditorsAnna R. Karlin
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770606
StatePublished - Jan 1 2018
Externally publishedYes
Event9th Innovations in Theoretical Computer Science, ITCS 2018 - Cambridge, United States
Duration: Jan 11 2018Jan 14 2018

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Other9th Innovations in Theoretical Computer Science, ITCS 2018
Country/TerritoryUnited States

All Science Journal Classification (ASJC) codes

  • Software


  • Contraction
  • Distance oracle
  • Spanner


Dive into the research topics of 'Distance-preserving graph contractions'. Together they form a unique fingerprint.

Cite this