2026-07-20T07:31:51Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8342 2024-03-06T10:42:09Z ddc:004 open_access

Distance-Preserving Graph Contractions Bernstein, Aaron Däubel, Karl Disser, Yann Klimm, Max Mütze, Torsten Smolny, Frieder distance oracle contraction spanner 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 the size of contractions, and find efficient algorithms to compute (non-optimal) contractions despite our hardness results. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Aaron Bernstein and Karl Däubel and Yann Disser and Max Klimm and Torsten Mütze and Frieder Smolny 2018 Is Part Of LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2018.51 urn:nbn:de:0030-drops-83427 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.51 eng https://creativecommons.org/licenses/by/3.0/legalcode