Distance-Preserving Graph Contractions

DOI10.1137/18M1169382MaRDI QIDQ5233754zbMATH OpenOpenAlexWikidataFDO

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

Publication date 6 September 2019

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1705.04544

zbMATH Keywords

contractionspannergraph compressiondistance oracle

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

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 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 $$, where $alphageq1$ and $$ 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.

Recommendations

• Distance-Preserving Graph Contractions
• Contraction distance between isomorphism classes of graphs
• A note on distance-preserving graph sparsification
• Preliminary results on distance-preserving graphs
• On constructing regular distance-preserving graphs
• Distance-preserving subgraphs of interval graphs
• Graphs preserving total distance upon vertex removal
• Contractions in persistence and metric graphs
• Graph contractions in vector-valued metric spaces and applications
• Distance preserving mappings of Grassmann graphs

Cites work

• scientific article; zbMATH DE number 2038725 (Why is no real title available?)
• scientific article; zbMATH DE number 1759406 (Why is no real title available?)
• scientific article; zbMATH DE number 3258067 (Why is no real title available?)
• A Tight Lower Bound for the Steiner Point Removal Problem on Trees
• Additive graph spanners
• Approximating spanners and directed Steiner forest: upper and lower bounds
• Better distance preservers and additive spanners
• Complexity of network synchronization
• Computing and Combinatorics
• Cyclic Scheduling via Integer Programs with Circular Ones
• Deterministic decremental single source shortest paths: beyond the \(O(mn)\) bound
• Distance-Preserving Graph Contractions
• Distance-Preserving Graph Contractions
• Extremal graphs with no \(C^{4,}\)s, \(C^{6,}\)s, or \(C^{10,}\)s
• Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
• Generating Sparse 2-Spanners
• Graph Minors for Preserving Terminal Distances Approximately - Lower and Upper Bounds
• Graph Partitioning and Graph Clustering
• Graph spanners
• Kron Reduction of Graphs With Applications to Electrical Networks
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Linear size distance preservers
• New constructions of \(({\alpha}, {\beta})\)-spanners and purely additive spanners
• On sparse spanners of weighted graphs
• On the hardness of approximating spanners
• Reducibility among combinatorial problems
• Sampling random spanning trees faster than matrix multiplication
• Sparse Sourcewise and Pairwise Distance Preservers
• Steiner points in tree metrics don't (really) help
• The 4/3 additive spanner exponent is tight
• Towards resistance sparsifiers

Cited in

(7)

• Distance-Preserving Graph Contractions
• Distance-Preserving Graph Contractions
• scientific article; zbMATH DE number 1222899 (Why is no real title available?)
• Improved guarantees for vertex sparsification in planar graphs
• The complexity of contracting bipartite graphs into small cycles
• Distance-preserving graph compression techniques
• Some aspects of graph sparsification in theory and practice

This page was built for publication: Distance-Preserving Graph Contractions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5233754)