Document Open Access Logo

Graph Minors for Preserving Terminal Distances Approximately - Lower and Upper Bounds

Authors Yun Kuen Cheung, Gramoz Goranci, Monika Henzinger

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.131.pdf
  • Filesize: 0.55 MB
  • 14 pages

Document Identifiers

Author Details

Yun Kuen Cheung
Gramoz Goranci
Monika Henzinger

Cite As Get BibTex

Yun Kuen Cheung, Gramoz Goranci, and Monika Henzinger. Graph Minors for Preserving Terminal Distances Approximately - Lower and Upper Bounds. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 131:1-131:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICALP.2016.131

Abstract

Given a graph where vertices are partitioned into k terminals and non-terminals, the goal is to compress the graph (i.e., reduce the number of non-terminals) using minor operations while preserving terminal distances approximately. The distortion of a compressed graph is the maximum multiplicative blow-up of distances between all pairs of terminals. We study the trade-off between the number of non-terminals and the distortion. This problem generalizes the Steiner Point Removal (SPR) problem, in which all non-terminals must be removed.

We introduce a novel black-box reduction to convert any lower bound on distortion for the SPR problem into a super-linear lower bound on the number of non-terminals, with the same distortion, for our problem. This allows us to show that there exist graphs such that every minor with distortion less than 2 / 2.5 / 3 must have Omega(k^2) / Omega(k^{5/4}) / Omega(k^{6/5}) non-terminals, plus more trade-offs in between. The black-box reduction has an interesting consequence: if the tight lower bound on distortion for the SPR problem is super-constant, then allowing any O(k) non-terminals will not help improving the lower bound to a constant.

We also build on the existing results on spanners, distance oracles and connected 0-extensions to show a number of upper bounds for general graphs, planar graphs, graphs that exclude a fixed minor and bounded treewidth graphs. Among others, we show that any graph admits a minor with O(log k) distortion and O(k^2) non-terminals, and any planar graph admits a minor with
1 + epsilon distortion and ~O((k/epsilon)^2) non-terminals.

Subject Classification

Keywords
  • Distance Approximating Minor
  • Graph Minor
  • Graph Compression
  • Vertex Sparsification
  • Metric Embedding

Metrics

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

References

  1. 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. Google Scholar
  2. Alexandr Andoni, Anupam Gupta, and Robert Krauthgamer. Towards (1 + eps)-approximate flow sparsifiers. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 279-293, 2014. URL: http://dx.doi.org/10.1137/1.9781611973402.20.
  3. Amitabh Basu and Anupam Gupta. Steiner point removal in graph metrics. http://www.ams.jhu.edu/∼abasu9/papers/SPR.pdf, 2008. Google Scholar
  4. T.-H. Chan, Donglin Xia, Goran Konjevod, and Andrea Richa. A tight lower bound for the steiner point removal problem on trees. In 9th International Workshop on Approximation, Randomization, and Combinatorial Optimization, APPROX'06/RANDOM'06, pages 70-81, Berlin, Heidelberg, 2006. Springer-Verlag. URL: http://dx.doi.org/10.1007/11830924_9.
  5. Moses Charikar, Tom Leighton, Shi Li, and Ankur Moitra. Vertex sparsifiers and abstract rounding algorithms. In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA, pages 265-274, 2010. URL: http://dx.doi.org/10.1109/FOCS.2010.32.
  6. Yang-Hua Chu, Sanjay G. Rao, and Hui Zhang. A case for end system multicast. In SIGMETRICS, pages 1-12, 2000. Google Scholar
  7. Julia Chuzhoy. On vertex sparsifiers with steiner nodes. In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19-22, 2012, pages 673-688, 2012. URL: http://dx.doi.org/10.1145/2213977.2214039.
  8. Don Coppersmith and Michael Elkin. Sparse sourcewise and pairwise distance preservers. SIAM J. Discrete Math., 20(2):463-501, 2006. URL: http://dx.doi.org/10.1137/050630696.
  9. Matthias Englert, Anupam Gupta, Robert Krauthgamer, Harald Räcke, Inbal Talgam-Cohen, and Kunal Talwar. Vertex sparsifiers: New results from old techniques. SIAM J. Comput., 43(4):1239-1262, 2014. URL: http://dx.doi.org/10.1137/130908440.
  10. Paul Erdös. Extremal problems in graph theory. Theory of Graphs and its Applications (Proc. Symposium Smolenice), 1963. Google Scholar
  11. Anupam Gupta. Steiner points in tree metrics don't (really) help. In Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, January 7-9, 2001, Washington, DC, USA., pages 220-227, 2001. URL: http://dl.acm.org/citation.cfm?id=365411.365448.
  12. Anupam Gupta, Amit Kumar, and Rajeev Rastogi. Traveling with a pez dispenser (or, routing issues in MPLS). SIAM J. Comput., 34(2):453-474, 2004. URL: http://dx.doi.org/10.1137/S0097539702409927.
  13. Lior Kamma, Robert Krauthgamer, and Huy L. Nguyen. Cutting corners cheaply, or how to remove steiner points. SIAM J. Comput., 44(4):975-995, 2015. Google Scholar
  14. Ken-ichi Kawarabayashi, Philip N. Klein, and Christian Sommer. Linear-space approximate distance oracles for planar, bounded-genus and minor-free graphs. In Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part I, pages 135-146, 2011. URL: http://dx.doi.org/10.1007/978-3-642-22006-7_12.
  15. 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
  16. Frank Thomson Leighton and Ankur Moitra. Extensions and limits to vertex sparsification. In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 47-56, 2010. URL: http://dx.doi.org/10.1145/1806689.1806698.
  17. Richard J. Lipton and Robert Endre Tarjan. A separator theorem for planar graphs. SIAM Journal on Applied Mathematics, 36(2):177-189, 1979. URL: http://dx.doi.org/10.1137/0136016.
  18. Konstantin Makarychev and Yury Makarychev. Metric extension operators, vertex sparsifiers and lipschitz extendability. In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA, pages 255-264, 2010. URL: http://dx.doi.org/10.1109/FOCS.2010.31.
  19. Ankur Moitra. Approximation algorithms for multicommodity-type problems with guarantees independent of the graph size. In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, October 25-27, 2009, Atlanta, Georgia, USA, pages 3-12, 2009. URL: http://dx.doi.org/10.1109/FOCS.2009.28.
  20. Harald Räcke. Optimal hierarchical decompositions for congestion minimization in networks. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008, pages 255-264, 2008. URL: http://dx.doi.org/10.1145/1374376.1374415.
  21. Harald Räcke, Chintan Shah, and Hanjo Täubig. Computing cut-based hierarchical decompositions in almost linear time. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 227-238, 2014. URL: http://dx.doi.org/10.1137/1.9781611973402.17.
  22. Michael Scharf, Gordon T. Wilfong, and Lisa Zhang. Sparsifying network topologies for application guidance. In IFIP/IEEE International Symposium on Integrated Network Management, IM 2015, Ottawa, ON, Canada, 11-15 May, 2015, pages 234-242, 2015. Google Scholar
  23. Andrew Thomason. An extremal function for contractions of graphs. Mathematical Proceedings of the Cambridge Philosophical Society, 95:261-265, 3 1984. Google Scholar
  24. Mikkel Thorup. Compact oracles for reachability and approximate distances in planar digraphs. J. ACM, 51(6):993-1024, 2004. URL: http://dx.doi.org/10.1145/1039488.1039493.
  25. 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. Google Scholar
  26. Richard M. Wilson. An existence theory for pairwise balanced designs, III: proof of the existence conjectures. J. Comb. Theory, Ser. A, 18(1):71-79, 1975. Google Scholar
  27. David P. Woodruff. Lower bounds for additive spanners, emulators, and more. In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21-24 October 2006, Berkeley, California, USA, Proceedings, pages 389-398, 2006. Google Scholar
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