Distance-Preserving Graph Contractions

DOI10.1137/18M1169382zbMATH Open1430.68177arXiv1705.04544OpenAlexW2971548643WikidataQ127320834 ScholiaQ127320834MaRDI QIDQ5233754FDOQ5233754

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)

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.

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

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

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)

Cites Work

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

Cited In (7)

• Distance-Preserving Graph Contractions
• Distance-Preserving Graph Contractions
• Title not available (Why is that?)
• 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)