Document Open Access Logo

Vertex Sparsification for Edge Connectivity in Polynomial Time

Author Yang P. Liu

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2023.83.pdf
  • Filesize: 0.72 MB
  • 15 pages

Document Identifiers

Author Details

Yang P. Liu
  • Department of Mathematics, Stanford University, CA, USA

Funding

This work was supported by the NDSEG Fellowship and the Google Research Fellowship.

Acknowledgements

The author would like to thank Yunbum Kook for feedback on an earlier version of this manuscript, anonymous reviewers for feedback to improve the presentation of this paper, and Richard Peng for useful discussions and encouragement.

Cite AsGet BibTex

Yang P. Liu. Vertex Sparsification for Edge Connectivity in Polynomial Time. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 83:1-83:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ITCS.2023.83

Abstract

An important open question in the area of vertex sparsification is whether (1+ε)-approximate cut-preserving vertex sparsifiers with size close to the number of terminals exist. The work [Parinya Chalermsook et al., 2021] (SODA 2021) introduced a relaxation called connectivity-c mimicking networks, which asks to construct a vertex sparsifier which preserves connectivity among k terminals exactly up to the value of c, and showed applications to dynamic connectivity data structures and survivable network design. We show that connectivity-c mimicking networks with Õ(kc³) edges exist and can be constructed in polynomial time in n and c, improving over the results of [Parinya Chalermsook et al., 2021] for any c ≥ log n, whose runtimes depended exponentially on c.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Paths and connectivity problems
Keywords
  • Vertex-sparsification
  • edge-connectivity
  • Gammoids

Metrics

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

References

  1. I. Abraham, D. Durfee, I. Koutis, S. Krinninger, and R. Peng. On fully dynamic graph sparsifiers. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 335-344, October 2016. Google Scholar
  2. Alexandr Andoni, Anupam Gupta, and Robert Krauthgamer. Towards (1+ ε)-approximate flow sparsifiers. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pages 279-293. Society for Industrial and Applied Mathematics, 2014. Google Scholar
  3. Sanjeev Arora, Elad Hazan, and Satyen Kale. Õ(√log n) approximation to SPARSEST CUT in Õ(n²) time. In 45th Symposium on Foundations of Computer Science (FOCS 2004), 17-19 October 2004, Rome, Italy, Proceedings, pages 238-247. IEEE Computer Society, 2004. URL: https://doi.org/10.1109/FOCS.2004.1.
  4. Sanjeev Arora, James R. Lee, and Assaf Naor. Euclidean distortion and the sparsest cut. In Harold N. Gabow and Ronald Fagin, editors, Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22-24, 2005, pages 553-562. ACM, 2005. URL: https://doi.org/10.1145/1060590.1060673.
  5. Sanjeev Arora, Satish Rao, and Umesh V. Vazirani. Expander flows, geometric embeddings and graph partitioning. J. ACM, 56(2):5:1-5:37, 2009. URL: https://doi.org/10.1145/1502793.1502794.
  6. András A. Benczúr and David R. Karger. Approximating s-t minimum cuts in Õ(n^2) time. In Gary L. Miller, editor, Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996, pages 47-55. ACM, 1996. URL: https://doi.org/10.1145/237814.237827.
  7. Parinya Chalermsook, Syamantak Das, Bundit Laekhanukit, Yunbum Kook, Yang P. Liu, Richard Peng, Mark Sellke, and Daniel Vaz. Vertex sparsification for edge connectivity. SODA, abs/2007.07862, 2021. URL: http://arxiv.org/abs/2007.07862.
  8. 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. Google Scholar
  9. Shiva Chaudhuri, K. V. Subrahmanyam, Frank Wagner, and Christos D. Zaroliagis. Computing mimicking networks. Algorithmica, 26(1):31-49, 2000. URL: https://doi.org/10.1007/s004539910003.
  10. Jeff Cheeger. A lower bound for the smallest eigenvalue of the Laplacian. In Problems in analysis (Papers dedicated to Salomon Bochner, 1969), pages 195-199. Princeton University Press, 1970. Google Scholar
  11. Paul Chew. There are planar graphs almost as good as the complete graph. J. Comput. Syst. Sci., 39(2):205-219, 1989. URL: https://doi.org/10.1016/0022-0000(89)90044-5.
  12. Timothy Chu, Yu Gao, Richard Peng, Sushant Sachdeva, Saurabh Sawlani, and Junxing Wang. Graph sparsification, spectral sketches, and faster resistance computation, via short cycle decompositions. In Mikkel Thorup, editor, 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 361-372. IEEE Computer Society, 2018. URL: https://doi.org/10.1109/FOCS.2018.00042.
  13. Julia Chuzhoy. On vertex sparsifiers with steiner nodes. In Howard J. Karloff and Toniann Pitassi, editors, Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012, pages 673-688. ACM, 2012. URL: https://doi.org/10.1145/2213977.2214039.
  14. Julia Chuzhoy, Yu Gao, Jason Li, Danupon Nanongkai, Richard Peng, and Thatchaphol Saranurak. A deterministic algorithm for balanced cut with applications to dynamic connectivity, flows, and beyond. CoRR, abs/1910.08025, 2019. URL: http://arxiv.org/abs/1910.08025.
  15. 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
  16. Gramoz Goranci, Monika Henzinger, and Pan Peng. Improved guarantees for vertex sparsification in planar graphs. In ESA, volume 87 of LIPIcs, pages 44:1-44:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. Google Scholar
  17. Torben Hagerup, Jyrki Katajainen, Naomi Nishimura, and Prabhakar Ragde. Characterizing multiterminal flow networks and computing flows in networks of small treewidth. Journal of Computer and System Sciences, 57(3):366-375, 1998. Google Scholar
  18. Han Jiang, Shang-En Huang, Thatchaphol Saranurak, and Tian Zhang. Vertex sparsifiers for hyperedge connectivity. In ESA, volume 244 of LIPIcs, pages 70:1-70:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. Google Scholar
  19. Wenyu Jin and Xiaorui Sun. Fully dynamic s-t edge connectivity in subpolynomial time (extended abstract). In FOCS, pages 861-872. IEEE, 2021. Google Scholar
  20. Nikolai Karpov, Marcin Pilipczuk, and Anna Zych-Pawlewicz. An exponential lower bound for cut sparsifiers in planar graphs. In Daniel Lokshtanov and Naomi Nishimura, editors, 12th International Symposium on Parameterized and Exact Computation, IPEC 2017, September 6-8, 2017, Vienna, Austria, volume 89 of LIPIcs, pages 24:1-24:11. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.IPEC.2017.24.
  21. Jonathan A. Kelner, Yin Tat Lee, Lorenzo Orecchia, and Aaron Sidford. An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 217-226, 2014. URL: https://doi.org/10.1137/1.9781611973402.16.
  22. Arindam Khan and Prasad Raghavendra. On mimicking networks representing minimum terminal cuts. Information Processing Letters, 114(7):365-371, 2014. Google Scholar
  23. Arindam Khan, Prasad Raghavendra, Prasad Tetali, and László A. Végh. On mimicking networks representing minimum terminal cuts. CoRR, abs/1207.6371, 2012. URL: http://arxiv.org/abs/1207.6371.
  24. Rohit Khandekar, Satish Rao, and Umesh V. Vazirani. Graph partitioning using single commodity flows. In Jon M. Kleinberg, editor, Proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, May 21-23, 2006, pages 385-390. ACM, 2006. URL: https://doi.org/10.1145/1132516.1132574.
  25. Stefan Kratsch and Magnus Wahlström. Representative sets and irrelevant vertices: New tools for kernelization. J. ACM, 67(3):16:1-16:50, 2020. URL: https://doi.org/10.1145/3390887.
  26. Robert Krauthgamer and Inbal Rika. Mimicking networks and succinct representations of terminal cuts. In Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms, pages 1789-1799. SIAM, 2013. Google Scholar
  27. Rasmus Kyng, Yin Tat Lee, Richard Peng, Sushant Sachdeva, and Daniel A. Spielman. Sparsified cholesky and multigrid solvers for connection laplacians. 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 842-850. ACM, 2016. URL: https://doi.org/10.1145/2897518.2897640.
  28. Rasmus Kyng, Richard Peng, Sushant Sachdeva, and Di Wang. Flows in almost linear time via adaptive preconditioning. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 902-913. ACM, 2019. URL: https://doi.org/10.1145/3313276.3316410.
  29. F Thomson Leighton and Ankur Moitra. Extensions and limits to vertex sparsification. In Proceedings of the forty-second ACM symposium on Theory of computing, pages 47-56. ACM, 2010. Google Scholar
  30. Tom Leighton and Satish Rao. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM, 46(6):787-832, 1999. URL: https://doi.org/10.1145/331524.331526.
  31. L. Lovász. Flats in matroids and geometric graphs. In Combinatorial surveys (Proc. Sixth British Combinatorial Conf., Royal Holloway Coll., Egham, 1977), pages 45-86, 1977. Google Scholar
  32. 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. Google Scholar
  33. Dániel Marx. A parameterized view on matroid optimization problems. Theor. Comput. Sci., 410(44):4471-4479, 2009. URL: https://doi.org/10.1016/j.tcs.2009.07.027.
  34. Ankur Moitra. Approximation algorithms for multicommodity-type problems with guarantees independent of the graph size. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science, pages 3-12. IEEE, 2009. Google Scholar
  35. Danupon Nanongkai and Thatchaphol Saranurak. Dynamic spanning forest with worst-case update time: adaptive, las vegas, and o(n^1/2-ε) time. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 1122-1129. ACM, 2017. URL: https://doi.org/10.1145/3055399.3055447.
  36. Danupon Nanongkai, Thatchaphol Saranurak, and Christian Wulff-Nilsen. Dynamic minimum spanning forest with subpolynomial worst-case update time. In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 950-961. IEEE Computer Society, 2017. Available at: URL: https://arxiv.org/abs/1708.03962.
  37. Harald Räcke, Chintan Shah, and Hanjo Täubig. Computing cut-based hierarchical decompositions in almost linear time. In Chandra Chekuri, editor, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 227-238. SIAM, 2014. URL: https://doi.org/10.1137/1.9781611973402.17.
  38. Thatchaphol Saranurak and Di Wang. Expander decomposition and pruning: Faster, stronger, and simpler. In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 2616-2635. SIAM, 2019. URL: https://doi.org/10.1137/1.9781611975482.162.
  39. Jonah Sherman. Breaking the multicommodity flow barrier for sqrt(log(n))-approximations to sparsest cut. CoRR, abs/0908.1379, 2009. URL: http://arxiv.org/abs/0908.1379.
  40. Daniel A. Spielman and Shang-Hua Teng. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In László Babai, editor, Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13-16, 2004, pages 81-90. ACM, 2004. URL: https://doi.org/10.1145/1007352.1007372.
  41. Magnus Wahlström. Quasipolynomial multicut-mimicking networks and kernels for multiway cut problems. ACM Trans. Algorithms, 18(2):15:1-15:19, 2022. Google Scholar
  42. Christian Wulff-Nilsen. Fully-dynamic minimum spanning forest with improved worst-case update time. In STOC, pages 1130-1143. ACM, 2017. 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