Document Open Access Logo

Distance-Preserving Graph Contractions

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

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2018.51.pdf
  • Filesize: 0.55 MB
  • 14 pages

Document Identifiers

Author Details

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

Cite As Get BibTex

Aaron Bernstein, Karl Däubel, Yann Disser, Max Klimm, Torsten Mütze, and Frieder Smolny. Distance-Preserving Graph Contractions. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 51:1-51:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ITCS.2018.51

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 \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.

Subject Classification

Keywords
  • distance oracle
  • contraction
  • spanner

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. A. Abboud and G. Bodwin. The 4/3 additive spanner exponent is tight. In STOC'16 - Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, pages 351-361. ACM, New York, 2016. Google Scholar
  2. Donald Aingworth, Chandra Chekuri, Piotr Indyk, and Rajeev Motwani. Fast estimation of diameter and shortest paths (without matrix multiplication). SIAM J. Comput., 28(4):1167-1181, 1999. URL: http://dx.doi.org/10.1137/S0097539796303421.
  3. Ingo Althöfer, Gautam Das, David P. Dobkin, Deborah Joseph, and José Soares. On sparse spanners of weighted graphs. Discrete & Computational Geometry, 9:81-100, 1993. URL: http://dx.doi.org/10.1007/BF02189308.
  4. Baruch Awerbuch. Complexity of network synchronization. J. ACM, 32(4):804-823, 1985. URL: http://dx.doi.org/10.1145/4221.4227.
  5. David A. Bader, Henning Meyerhenke, Peter Sanders, and Dorothea Wagner, editors. Graph Partitioning and Graph Clustering, 10th DIMACS Implementation Challenge Workshop, Georgia Institute of Technology, Atlanta, GA, USA, February 13-14, 2012. Proceedings, volume 588 of Contemporary Mathematics. American Mathematical Society, 2013. URL: http://dx.doi.org/10.1090/conm/588.
  6. S. Baswana, T. Kavitha, K. Mehlhorn, and S. Pettie. New constructions of (α,β)-spanners and purely additive spanners. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 672-681. ACM, New York, 2005. Google Scholar
  7. Surender Baswana and Sandeep Sen. A simple linear time algorithm for computing a (2k-1)-spanner of o(n^1+1/k) size in weighted graphs. In Jos C. M. Baeten, Jan Karel Lenstra, Joachim Parrow, and Gerhard J. Woeginger, editors, Automata, Languages and Programming, 30th International Colloquium, ICALP 2003, Eindhoven, The Netherlands, June 30 - July 4, 2003. Proceedings, volume 2719 of Lecture Notes in Computer Science, pages 384-296. Springer, 2003. URL: http://dx.doi.org/10.1007/3-540-45061-0_32.
  8. Aaron Bernstein and Shiri Chechik. Deterministic decremental single source shortest paths: beyond the o(mn) bound. In Daniel Wichs and Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 389-397. ACM, 2016. URL: http://dx.doi.org/10.1145/2897518.2897521.
  9. Hubert T.-H. Chan, Donglin Xia, Goran Konjevod, and Andréa W. Richa. A tight lower bound for the steiner point removal problem on trees. In Josep Díaz, Klaus Jansen, José D. P. Rolim, and Uri Zwick, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 and 10th International Workshop on Randomization and Computation, RANDOM 2006, Barcelona, Spain, August 28-30 2006, Proceedings, volume 4110 of Lecture Notes in Computer Science, pages 70-81. Springer, 2006. URL: http://dx.doi.org/10.1007/11830924_9.
  10. Yun Kuen Cheung, Gramoz Goranci, and Monika Henzinger. Graph minors for preserving terminal distances approximately - lower and upper bounds. In Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi, editors, 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, volume 55 of LIPIcs, pages 131:1-131:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2016.131.
  11. E. Chlamtáč, M. Dinitz, G. Kortsarz, and B. Laekhanukit. Approximating spanners and directed steiner forest: Upper and lower bounds. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '17, pages 534-553, Philadelphia, PA, USA, 2017. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=3039686.3039720.
  12. Karl Däubel, Yann Disser, Max Klimm, Torsten Mütze, and Frieder Smolny. Distance-preserving graph contractions. CoRR, abs/1705.04544, 2017. URL: http://arxiv.org/abs/1705.04544.
  13. P. Erdős. Extremal problems in graph theory. In Theory of Graphs and its Applications (Proc. Sympos. Smolenice, 1963), pages 29-36. Publ. House Czechoslovak Acad. Sci., Prague, 1964. Google Scholar
  14. A. Gupta. Steiner points in tree metrics don't (really) help. In Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (Washington, DC, 2001), pages 220-227. SIAM, Philadelphia, PA, 2001. Google Scholar
  15. G. Kortsarz. On the hardness of approximation spanners. In Proceedings of the International Workshop on Approximation Algorithms for Combinatorial Optimization, APPROX '98, pages 135-146, London, UK, UK, 1998. Springer-Verlag. URL: http://dl.acm.org/citation.cfm?id=646687.756924.
  16. Guy Kortsarz and David Peleg. Generating sparse 2-spanners. J. Algorithms, 17(2):222-236, 1994. URL: http://dx.doi.org/10.1006/jagm.1994.1032.
  17. Robert Krauthgamer, Huy L. Nguyen, and Tamar Zondiner. Preserving terminal distances using minors. SIAM J. Discrete Math., 28(1):127-141, 2014. URL: http://dx.doi.org/10.1137/120888843.
  18. Arthur L. Liestman and Thomas C. Shermer. Additive graph spanners. Networks, 23(4):343-363, 1993. URL: http://dx.doi.org/10.1002/net.3230230417.
  19. David Peleg and Alejandro A. Schäffer. Graph spanners. Journal of Graph Theory, 13(1):99-116, 1989. URL: http://dx.doi.org/10.1002/jgt.3190130114.
  20. Rephael Wenger. Extremal graphs with no C^4’s, C^6’s, or C^10’s. J. Comb. Theory, Ser. B, 52(1):113-116, 1991. URL: http://dx.doi.org/10.1016/0095-8956(91)90097-4.
  21. David Zuckerman. Linear degree extractors and the inapproximability of max clique and chromatic number. Theory of Computing, 3(1):103-128, 2007. URL: http://dx.doi.org/10.4086/toc.2007.v003a006.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact