Document Open Access Logo

Improved Guarantees for Vertex Sparsification in Planar Graphs

Authors Gramoz Goranci, Monika Henzinger, Pan Peng

PDF
Thumbnail PDF

File

LIPIcs.ESA.2017.44.pdf
  • Filesize: 0.56 MB
  • 14 pages

Document Identifiers

Author Details

Gramoz Goranci
Monika Henzinger
Pan Peng

Cite AsGet BibTex

Gramoz Goranci, Monika Henzinger, and Pan Peng. Improved Guarantees for Vertex Sparsification in Planar Graphs. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 44:1-44:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.ESA.2017.44

Abstract

Graph Sparsification aims at compressing large graphs into smaller ones while (approximately) preserving important characteristics of the input graph. In this work we study Vertex Sparsifiers, i.e., sparsifiers whose goal is to reduce the number of vertices. Given a weighted graph G=(V,E), and a terminal set K with |K|=k, a quality-q vertex cut sparsifier of G is a graph H with K contained in V_H that preserves the value of minimum cuts separating any bipartition of K, up to a factor of q. We show that planar graphs with all the k terminals lying on the same face admit quality-1 vertex cut sparsifier of size O(k^2) that are also planar. Our result extends to vertex flow and distance sparsifiers. It improves the previous best known bound of O(k^2 2^(2k)) for cut and flow sparsifiers by an exponential factor, and matches an Omega(k^2) lower-bound for this class of graphs. We also study vertex reachability sparsifiers for directed graphs. Given a digraph G=(V,E) and a terminal set K, a vertex reachability sparsifier of G is a digraph H=(V_H,E_H), K contained in V_H that preserves all reachability information among terminal pairs. We introduce the notion of reachability-preserving minors, i.e., we require H to be a minor of G. Among others, for general planar digraphs, we construct reachability-preserving minors of size O(k^2 log^2 k). We complement our upper-bound by showing that there exists an infinite family of acyclic planar digraphs such that any reachability-preserving minor must have Omega(k^2) vertices.
Keywords
  • Vertex Sparsification
  • Graph Sparsification
  • Planar Graphs
  • Metric Embedding
  • Reachability

Metrics

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

References

  1. Alfred V. Aho, M. R. Garey, and Jeffrey D. Ullman. The transitive reduction of a directed graph. SIAM J. Comput., 1(2):131-137, 1972. Google Scholar
  2. Alexandr Andoni, Anupam Gupta, and Robert Krauthgamer. Towards (1+ ε)-approximate flow sparsifiers. In Proc. of the 25th SODA, pages 279-293, 2014. Google Scholar
  3. András A. Benczúr and David R. Karger. Approximating s-t minimum cuts in Õ(n^2) time. In Proc. of the 28th STOC, pages 47-55, 1996. Google Scholar
  4. Greg Bodwin. Linear size distance preservers. In Proc. of the 28th SODA, pages 600-615, 2017. Google Scholar
  5. T-H Hubert Chan, Donglin Xia, Goran Konjevod, and Andrea Richa. A tight lower bound for the steiner point removal problem on trees. In Proc. of the 9th APPROX/RANDOM, pages 70-81, 2006. Google Scholar
  6. Moses Charikar, Tom Leighton, Shi Li, and Ankur Moitra. Vertex sparsifiers and abstract rounding algorithms. In Proc. of the 51th FOCS, pages 265-274, 2010. Google Scholar
  7. Chandra Chekuri, Anupam Gupta, Ilan Newman, Yuri Rabinovich, and Alistair Sinclair. Embedding k-outerplanar graphs into l1. SIAM J. Discrete Math., 20(1):119-136, 2006. Google Scholar
  8. Chandra Chekuri, Sanjeev Khanna, and F Bruce Shepherd. Edge-disjoint paths in planar graphs with constant congestion. SIAM J. Comput., 39(1):281-301, 2009. Google Scholar
  9. Chandra Chekuri, F Bruce Shepherd, and Christophe Weibel. Flow-cut gaps for integer and fractional multiflows. In Proc. of the 21st SODA, pages 1198-1208, 2010. Google Scholar
  10. Yun Kuen Cheung, Gramoz Goranci, and Monika Henzinger. Graph minors for preserving terminal distances approximately - Lower and Upper Bounds. In Proc. of the 43rd ICALP, pages 131:1-131:14, 2016. Google Scholar
  11. Julia Chuzhoy. On vertex sparsifiers with steiner nodes. In Proc. of the 44th STOC, pages 673-688, 2012. Google Scholar
  12. Julia Chuzhoy. Routing in undirected graphs with constant congestion. In Proc. of the 44th STOC, pages 855-874, 2012. Google Scholar
  13. Don Coppersmith and Michael Elkin. Sparse sourcewise and pairwise distance preservers. SIAM J. Discrete Math., 20(2):463-501, 2006. Google Scholar
  14. Edward B Curtis, David Ingerman, and James A Morrow. Circular planar graphs and resistor networks. Linear algebra and its applications, 283(1):115-150, 1998. Google Scholar
  15. Krzysztof Diks and Piotr Sankowski. Dynamic plane transitive closure. In Proc. of the 15th ESA, pages 594-604, 2007. Google Scholar
  16. Michael Elkin, Arnold Filtser, and Ofer Neiman. Terminal embeddings. In Proc. of the 18th APPROX/RANDOM, pages 242-264, 2015. Google Scholar
  17. 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. Google Scholar
  18. Thomas A Feo and J Scott Provan. Delta-wye transformations and the efficient reduction of two-terminal planar graphs. Operations Research, 41(3):572-582, 1993. Google Scholar
  19. Isidoro Gitler. Delta-Wye-Delta Transformations: Algorithms and Applications. PhD thesis, Department of Combinatorics and Optimization, University of Waterloo, 1991. Google Scholar
  20. Gramoz Goranci and Harald Räcke. Vertex sparsification in trees. In Proc. of the 14th WAOA, pages 103-115, 2016. Google Scholar
  21. Anupam Gupta. Steiner points in tree metrics don't (really) help. In Proc. of the 12th SODA, pages 220-227, 2001. Google Scholar
  22. Torben Hagerup, Jyrki Katajainen, Naomi Nishimura, and Prabhakar Ragde. Characterizing multiterminal flow networks and computing flows in networks of small treewidth. J. Comput. Syst. Sci., 57(3):366-375, 1998. Google Scholar
  23. 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
  24. Irit Katriel, Martin Kutz, and Martin Skutella. Reachability substitutes for planar digraphs. In Technical Report MPI-I-2005-1-002. Max-Planck-Institut für Informatik, 2005. Google Scholar
  25. Arindam Khan and Prasad Raghavendra. On mimicking networks representing minimum terminal cuts. Inf. Process. Lett., 114(7):365-371, 2014. Google Scholar
  26. Robert Krauthgamer, Huy L Nguyen, and Tamar Zondiner. Preserving terminal distances using minors. SIAM J. Discrete Math., 28(1):127-141, 2014. Google Scholar
  27. Robert Krauthgamer and Inbal Rika. Mimicking networks and succinct representations of terminal cuts. In Proc. of the 24th SODA, pages 1789-1799, 2013. Google Scholar
  28. Robert Krauthgamer and Inbal Rika. Refined vertex sparsifiers of planar graphs. CoRR, abs/1702.05951, 2017. Google Scholar
  29. Robert Krauthgamer and Tamar Zondiner. Preserving terminal distances using minors. In Proc. of the 39th ICALP, pages 594-605, 2012. Google Scholar
  30. James R Lee, Manor Mendel, and Mohammad Moharrami. A node-capacitated okamura-seymour theorem. In Proc. of the 45th STOC, pages 495-504, 2013. Google Scholar
  31. Frank Thomson Leighton and Ankur Moitra. Extensions and limits to vertex sparsification. In Proc. of the 42nd STOC, pages 47-56, 2010. Google Scholar
  32. Konstantin Makarychev and Yury Makarychev. Metric extension operators, vertex sparsifiers and lipschitz extendability. In Proc. of the 51th FOCS, pages 255-264, 2010. Google Scholar
  33. Jiří Matoušek. On the distortion required for embedding finite metric spaces into normed spaces. Israel Journal of Mathematics, 93(1):333-344, 1996. Google Scholar
  34. Ankur Moitra. Approximation algorithms for multicommodity-type problems with guarantees independent of the graph size. In Proc. of the 50th FOCS, 2009. Google Scholar
  35. Haruko Okamura and Paul D. Seymour. Multicommodity flows in planar graphs. J. Comb. Theory, Ser. B, 31(1):75-81, 1981. Google Scholar
  36. Daniel A. Spielman and Shang-Hua Teng. Spectral sparsification of graphs. SIAM J. Comput., 40(4):981-1025, 2011. Google Scholar
  37. Sairam Subramanian. A fully dynamic data structure for reachability in planar digraphs. In Proc. of the 1st ESA, pages 372-383, 1993. Google Scholar
  38. Roberto Tamassia and Ioannis G Tollis. Planar grid embedding in linear time. IEEE Trans. Circuits Syst., 36(9):1230-1234, 1989. Google Scholar
  39. Mikkel Thorup. Compact oracles for reachability and approximate distances in planar digraphs. J. ACM, 51(6):993-1024, 2004. Google Scholar
  40. Mikkel Thorup and Uri Zwick. Approximate distance oracles. J. ACM, 52(1):1-24, 2005. Google Scholar
  41. Leslie G. Valiant. Universality considerations in VLSI circuits. IEEE Trans. Computers, 30(2):135-140, 1981. 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 Imprint Privacy Contact