Document Open Access Logo

O(1) Steiner Point Removal in Series-Parallel Graphs

Authors D. Ellis Hershkowitz, Jason Li

PDF

File

Thumbnail PDF
PDF
LIPIcs.ESA.2022.66.pdf
  • Filesize: 1.02 MB
  • 17 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Sparsification and spanners
  • Theory of computation → Shortest paths
  • Theory of computation → Approximation algorithms analysis
Keywords
  • Metric embeddings
  • graph algorithms
  • vertex sparsification

Metrics

Abstract

We study how to vertex-sparsify a graph while preserving both the graph’s metric and structure. Specifically, we study the Steiner point removal (SPR) problem where we are given a weighted graph G = (V,E,w) and terminal set V' ⊆ V and must compute a weighted minor G' = (V',E', w') of G which approximates G’s metric on V'. A major open question in the area of metric embeddings is the existence of O(1) multiplicative distortion SPR solutions for every (non-trivial) minor-closed family of graphs. To this end prior work has studied SPR on trees, cactus and outerplanar graphs and showed that in these graphs such a minor exists with O(1) distortion.
We give O(1) distortion SPR solutions for series-parallel graphs, extending the frontier of this line of work. The main engine of our approach is a new metric decomposition for series-parallel graphs which we call a hammock decomposition. Roughly, a hammock decomposition is a forest-like structure that preserves certain critical parts of the metric induced by a series-parallel graph.

Cite As Get BibTex

D. Ellis Hershkowitz and Jason Li. O(1) Steiner Point Removal in Series-Parallel Graphs. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 66:1-66:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ESA.2022.66

Author Details

D. Ellis Hershkowitz
  • Carnegie Mellon University, Pittsburgh, PA, USA
Jason Li
  • Berkeley, CA, USA

Funding

Supported in part by NSF grants CCF-1527110, CCF-1618280, CCF-1814603, CCF-1910588, NSF CAREER award CCF-1750808, a Sloan Research Fellowship, funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation program (ERC grant agreement 949272) and Swiss National Foundation (project grant 200021-184735).
  • Hershkowitz, D. Ellis: Supported by the Air Force Office of Scientific Research under award number FA9550-20-1-0080.

References

  1. Reyan Ahmed, Greg Bodwin, Faryad Darabi Sahneh, Keaton Hamm, Mohammad Javad Latifi Jebelli, Stephen Kobourov, and Richard Spence. Graph spanners: A tutorial review. Computer Science Review, 37:100253, 2020. Google Scholar
  2. Ingo Althöfer, Gautam Das, David Dobkin, Deborah Joseph, and José Soares. On sparse spanners of weighted graphs. Discrete & Computational Geometry, 9(1):81-100, 1993. Google Scholar
  3. Sanjeev Arora, Michelangelo Grigni, David R Karger, Philip N Klein, and Andrzej Woloszyn. A polynomial-time approximation scheme for weighted planar graph tsp. In Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), volume 98, pages 33-41, 1998. Google Scholar
  4. Yair Bartal. Probabilistic approximation of metric spaces and its algorithmic applications. In Symposium on Foundations of Computer Science (FOCS), pages 184-193. IEEE, 1996. Google Scholar
  5. Amitabh Basu and Anupam Gupta. Steiner point removal in graph metrics, 2008. Unpublished Manuscript, available from URL: https://www.ams.jhu.edu/~abasu9/papers/SPR.pdf.
  6. Hans L Bodlaender. A partial k-arboretum of graphs with bounded treewidth. Theoretical computer science, 209(1-2):1-45, 1998. Google Scholar
  7. Bo Brinkman, Adriana Karagiozova, and James R Lee. Vertex cuts, random walks, and dimension reduction in series-parallel graphs. In Annual ACM Symposium on Theory of Computing (STOC), pages 621-630, 2007. Google Scholar
  8. T-H Hubert Chan, Donglin Xia, Goran Konjevod, and Andrea Richa. A tight lower bound for the steiner point removal problem on trees. In International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pages 70-81. Springer, 2006. Google Scholar
  9. Chandra Chekuri, Anupam Gupta, Ilan Newman, Yuri Rabinovich, and Alistair Sinclair. Embedding k-outerplanar graphs into l1. SIAM Journal on Discrete Mathematics, 20(1):119-136, 2006. Google Scholar
  10. Yun Kuen Cheung. Steiner point removal—distant terminals don't (really) bother. In Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1353-1360. SIAM, 2018. Google Scholar
  11. Yun Kuen Cheung, Gramoz Goranci, and Monika Henzinger. Graph minors for preserving terminal distances approximately-lower and upper bounds. In International Colloquium on Automata, Languages and Programming (ICALP), 2016. Google Scholar
  12. Richard J Duffin. Topology of series-parallel networks. Journal of Mathematical Analysis and Applications, 10(2):303-318, 1965. Google Scholar
  13. Yuval Emek and David Peleg. A tight upper bound on the probabilistic embedding of series-parallel graphs. SIAM Journal on Discrete Mathematics, 23(4):1827-1841, 2010. Google Scholar
  14. Matthias Englert, Anupam Gupta, Robert Krauthgamer, Harald Racke, Inbal Talgam-Cohen, and Kunal Talwar. Vertex sparsifiers: New results from old techniques. SIAM Journal on Computing, 43(4):1239-1262, 2014. Google Scholar
  15. David Eppstein. Parallel recognition of series-parallel graphs. Information and Computation, 98(1):41-55, 1992. Google Scholar
  16. Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar. A tight bound on approximating arbitrary metrics by tree metrics. Journal of Computer and System Sciences, 69(3):485-497, 2004. Google Scholar
  17. Arnold Filtser. Steiner point removal with distortion o (log k). In Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1361-1373. SIAM, 2018. Google Scholar
  18. Arnold Filtser. Steiner point removal with distortion o(log k), using the noisy-voronoi algorithm. arXiv preprint, 2018. URL: http://arxiv.org/abs/1808.02800.
  19. Arnold Filtser. Scattering and sparse partitions, and their applications. In International Colloquium on Automata, Languages and Programming (ICALP), 2020. Google Scholar
  20. Arnold Filtser, Robert Krauthgamer, and Ohad Trabelsi. Relaxed voronoi: A simple framework for terminal-clustering problems. In SIAM Symposium on Simplicity in Algorithms (SOSA), 2018. Google Scholar
  21. Gramoz Goranci, Monika Henzinger, and Pan Peng. Improved guarantees for vertex sparsification in planar graphs. SIAM Journal on Discrete Mathematics, 34(1):130-162, 2020. Google Scholar
  22. Anupam Gupta. Steiner points in tree metrics don't (really) help. In Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 682-690, 2001. Google Scholar
  23. Anupam Gupta, Robert Krauthgamer, and James R Lee. Bounded geometries, fractals, and low-distortion embeddings. In Symposium on Foundations of Computer Science (FOCS), pages 534-543. IEEE, 2003. Google Scholar
  24. Anupam Gupta, Ilan Newman, Yuri Rabinovich, and Alistair Sinclair. Cuts, trees and l/sub 1/-embeddings of graphs. In Symposium on Foundations of Computer Science (FOCS), pages 399-408. IEEE, 1999. Google Scholar
  25. Anupam Gupta, Ilan Newman, Yuri Rabinovich, and Alistair Sinclair. Cuts, trees and l1-embeddings of graphs. Combinatorica, 24(2):233-269, 2004. Google Scholar
  26. Frank Hadlock. Finding a maximum cut of a planar graph in polynomial time. SIAM Journal on Computing, 4(3):221-225, 1975. Google Scholar
  27. Lior Kamma, Robert Krauthgamer, and Huy L Nguyen. Cutting corners cheaply, or how to remove steiner points. SIAM Journal on Computing, 44(4):975-995, 2015. Google Scholar
  28. Samir Khuller. Ear decompositions. SigAct News, 20(1):128, 1989. Google Scholar
  29. Philip Klein, Serge A Plotkin, and Satish Rao. Excluded minors, network decomposition, and multicommodity flow. In Annual ACM Symposium on Theory of Computing (STOC), pages 682-690, 1993. Google Scholar
  30. Robert Krauthgamer, Huy L Nguyen, and Tamar Zondiner. Preserving terminal distances using minors. SIAM Journal on Discrete Mathematics, 28(1):127-141, 2014. Google Scholar
  31. Robert Krauthgamer and Havana Inbal Rika. Refined vertex sparsifiers of planar graphs. SIAM Journal on Discrete Mathematics, 34(1):101-129, 2020. Google Scholar
  32. James R. Lee and Cyrus Rashtchian. A simpler proof of the kpr theorem. https://tcsmath.wordpress.com/tag/klein-plotkin-rao/, January 2012.
  33. Haruko Okamura and Paul D Seymour. Multicommodity flows in planar graphs. Journal of Combinatorial Theory, Series B, 31(1):75-81, 1981. Google Scholar
  34. Neil Robertson and Paul D Seymour. Graph minors. xx. wagner’s conjecture. Journal of Combinatorial Theory, Series B, 92(2):325-357, 2004. Google Scholar
  35. Liam Roditty, Mikkel Thorup, and Uri Zwick. Deterministic constructions of approximate distance oracles and spanners. In International Colloquium on Automata, Languages and Programming (ICALP), pages 261-272. Springer, 2005. Google Scholar
  36. Mikkel Thorup and Uri Zwick. Approximate distance oracles. Journal of the ACM (JACM), 52(1):1-24, 2005. Google Scholar
  37. Thomas Victor Wimer. Linear algorithms on k-terminal graphs. PhD Thesis, 1987. AAI8803914. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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