Document Open Access Logo

Isolating Cuts, (Bi-)Submodularity, and Faster Algorithms for Connectivity

Authors Chandra Chekuri, Kent Quanrud

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2021.50.pdf
  • Filesize: 0.91 MB
  • 20 pages

Document Identifiers

Author Details

Chandra Chekuri
  • University of Illinois at Urbana-Champaign, IL, USA
Kent Quanrud
  • Purdue University, West Lafayette, IN, USA

Funding

  • Chekuri, Chandra: Supported in part by NSF grants CCF-1910149 and CCF-1907937.

Acknowledgements

We thank the reviewers for their helpful comments.

Cite AsGet BibTex

Chandra Chekuri and Kent Quanrud. Isolating Cuts, (Bi-)Submodularity, and Faster Algorithms for Connectivity. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 50:1-50:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ICALP.2021.50

Abstract

Li and Panigrahi [Jason Li and Debmalya Panigrahi, 2020], in recent work, obtained the first deterministic algorithm for the global minimum cut of a weighted undirected graph that runs in time o(mn). They introduced an elegant and powerful technique to find isolating cuts for a terminal set in a graph via a small number of s-t minimum cut computations. In this paper we generalize their isolating cut approach to the abstract setting of symmetric bisubmodular functions (which also capture symmetric submodular functions). Our generalization to bisubmodularity is motivated by applications to element connectivity and vertex connectivity. Utilizing the general framework and other ideas we obtain significantly faster randomized algorithms for computing global (and subset) connectivity in a number of settings including hypergraphs, element connectivity and vertex connectivity in graphs, and for symmetric submodular functions.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
Keywords
  • cuts
  • vertex connectivity
  • hypergraphs
  • fast algorithms
  • submodularity
  • bisumodularity
  • lattices
  • isolating cuts
  • element connectivity

Metrics

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

Related Versions

References

  1. Ashkan Aazami, Joseph Cheriyan, and Krishnam Raju Jampani. Approximation algorithms and hardness results for packing element-disjoint steiner trees in planar graphs. Algorithmica, 63(1-2):425-456, 2012. Google Scholar
  2. Kazutoshi Ando and Satoru Fujishige. On structures of bisubmodular polyhedra. Math. Program., 74:293-317, 1996. Google Scholar
  3. Kazutoshi Ando, Satoru Fujishige, and Takeshi Naitoh. A characterization of bisubmodular functions. Discret. Math., 148(1-3):299-303, 1996. Google Scholar
  4. André Bouchet. Greedy algorithm and symmetric matroids. Math. Program., 38(2):147-159, 1987. Google Scholar
  5. Gruia Călinescu, Chandra Chekuri, and Jan Vondrák. Disjoint bases in a polymatroid. Random Structures & Algorithms, 35(4):418-430, 2009. Google Scholar
  6. Ruoxu Cen, Jason Li, Danupon Nanongkai, Debmalya Panigrahi, and Thatchaphol Saranurak. Minimum cuts in directed graphs via √n max-flows. CoRR, abs/2104.07898, 2021. URL: http://arxiv.org/abs/2104.07898.
  7. Chandra Chekuri. Some open problems in element connectivity, September 2015. URL: http://chekuri.cs.illinois.edu/papers/elem-connectivity-open-probs.pdf.
  8. Chandra Chekuri and Nitish Korula. A graph reduction step preserving element-connectivity and packing steiner trees and forests. SIAM Journal on Discrete Mathematics, 28(2):577-597, 2014. Google Scholar
  9. Chandra Chekuri and Kent Quanrud. Faster algorithms for rooted connectivity in directed graphs, 2021. To appear in ICALP,. URL: http://arxiv.org/abs/2104.07205.
  10. Chandra Chekuri and Kent Quanrud. Isolating cuts, (bi-)submodularity, and faster algorithms for global connectivity problems. CoRR, abs/2103.12908, 2021. URL: http://arxiv.org/abs/2103.12908.
  11. Chandra Chekuri, Thapanapong Rukkanchanunt, and Chao Xu. On element-connectivity preserving graph simplification. In Nikhil Bansal and Irene Finocchi, editors, Algorithms - ESA 2015 - 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings, volume 9294 of Lecture Notes in Computer Science, pages 313-324. Springer, 2015. Google Scholar
  12. Chandra Chekuri and Chao Xu. Minimum cuts and sparsification in hypergraphs. SIAM Journal on Computing, 47(6):2118-2156, 2018. Google Scholar
  13. Joseph Cheriyan and Mohammad R Salavatipour. Packing element-disjoint steiner trees. ACM Transactions on Algorithms (TALG), 3(4):47-es, 2007. Google Scholar
  14. Joseph Cheriyan, Santosh Vempala, and Adrian Vetta. Network design via iterative rounding of setpair relaxations. Combinatorica, 26(3):255-275, 2006. Google Scholar
  15. Julia Chuzhoy and Sanjeev Khanna. An o (k³ log n)-approximation algorithm for vertex-connectivity survivable network design. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science, pages 437-441. IEEE, 2009. Google Scholar
  16. Lisa Fleischer, Kamal Jain, and David P Williamson. Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems. Journal of Computer and System Sciences, 72(5):838-867, 2006. Google Scholar
  17. Sebastian Forster, Danupon Nanongkai, Liu Yang, Thatchaphol Saranurak, and Sorrachai Yingchareonthawornchai. Computing and testing small connectivity in near-linear time and queries via fast local cut algorithms. In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 2046-2065. SIAM, 2020. Google Scholar
  18. Kyle Fox, Debmalya Panigrahi, and Fred Zhang. Minimum cut and minimum k-cut in hypergraphs via branching contractions. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 881-896. SIAM, 2019. Google Scholar
  19. Satoru Fujishige and Satoru Iwata. Bisubmodular function minimization. SIAM J. Discret. Math., 19(4):1065-1073, 2005. Google Scholar
  20. Harold N. Gabow. Using expander graphs to find vertex connectivity. J. ACM, 53(5):800-844, 2006. Google Scholar
  21. Pawel Gawrychowski, Shay Mozes, and Oren Weimann. Minimum cut in (m log² n) time. In Artur Czumaj, Anuj Dawar, and Emanuela Merelli, editors, 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference), volume 168 of LIPIcs, pages 57:1-57:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. Google Scholar
  22. Andrew V. Goldberg and Robert E. Tarjan. Finding minimum-cost circulations by successive approximation. Math. Oper. Res., 15(3):430-466, 1990. Google Scholar
  23. Anupam Gupta and Jochen Könemann. Approximation algorithms for network design: A survey. Surveys in Operations Research and Management Science, 16(1):3-20, 2011. Google Scholar
  24. Jianxiu Hao and James B. Orlin. A faster algorithm for finding the minimum cut in a directed graph. J. Algorithms, 17(3):424-446, 1994. Google Scholar
  25. Ramesh Hariharan, Telikepalli Kavitha, Debmalya Panigrahi, and Anand Bhalgat. An Õ(mn) gomory-hu tree construction algorithm for unweighted graphs. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 605-614, 2007. Google Scholar
  26. Monika Rauch Henzinger. A static 2-approximation algorithm for vertex connectivity and incremental approximation algorithms for edge and vertex connectivity. Journal of Algorithms, 24(1):194-220, 1997. Google Scholar
  27. Monika Rauch Henzinger, Satish Rao, and Harold N. Gabow. Computing vertex connectivity: New bounds from old techniques. J. Algorithms, 34(2):222-250, 2000. Google Scholar
  28. Kamal Jain, Ion Măndoiu, Vijay V Vazirani, and David P Williamson. A primal-dual schema based approximation algorithm for the element connectivity problem. Journal of Algorithms, 45(1):1-15, 2002. Google Scholar
  29. Stephen Jue and Philip N. Klein. A near-linear time minimum steiner cut algorithm for planar graphs, 2019. URL: http://arxiv.org/abs/1912.11103.
  30. David R Karger. Minimum cuts in near-linear time. Journal of the ACM (JACM), 47(1):46-76, 2000. Google Scholar
  31. Tarun Kathuria, Yang P. Liu, and Aaron Sidford. Unit capacity maxflow in almost $o(mˆ{4/3})$ time. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 119-130. IEEE, 2020. Google Scholar
  32. Regina Klimmek and Frank Wagner. A simple hypergraph min cut algorithm. Technical Report B 96-02, Bericht FU Berlin Fachbereich Mathematik und Informatik, 1996. Google Scholar
  33. Guy Kortsarz and Zeev Nutov. Approximating minimum cost connectivity problems. In Dagstuhl Seminar Proceedings. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2010. Google Scholar
  34. Yin Tat Lee and Aaron Sidford. Path finding methods for linear programming: Solving linear programs in Õ(√rank) iterations and faster algorithms for maximum flow. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 424-433. IEEE Computer Society, 2014. Google Scholar
  35. Yin Tat Lee, Aaron Sidford, and Sam Chiu-wai Wong. A faster cutting plane method and its implications for combinatorial and convex optimization. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 1049-1065. IEEE, 2015. Google Scholar
  36. Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak, and Sorrachai Yingchareonthawornchai. Vertex connectivity in poly-logarithmic max-flows, 2021. To appear in ACM STOC,. Google Scholar
  37. Jason Li and Debmalya Panigrahi. Deterministic min-cut in poly-logarithmic max-flows. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 85-92. IEEE, 2020. Google Scholar
  38. Nathan Linial, László Lovász, and Avi Wigderson. Rubber bands, convex embeddings and graph connectivity. Comb., 8(1):91-102, 1988. Google Scholar
  39. Yang P. Liu and Aaron Sidford. Faster energy maximization for faster maximum flow. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 803-814. ACM, 2020. Google Scholar
  40. Aleksander Madry. Computing maximum flow with augmenting electrical flows. In Irit Dinur, editor, IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 593-602. IEEE Computer Society, 2016. Google Scholar
  41. Wai-Kei Mak and D.F. Wong. A fast hypergraph min-cut algorithm for circuit partitioning. Integration, the VLSI Journal, 30(1):1-11, 2000. Google Scholar
  42. Sagnik Mukhopadhyay and Danupon Nanongkai. Weighted min-cut: sequential, cut-query, and streaming algorithms. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 496-509. ACM, 2020. Google Scholar
  43. Sagnik Mukhopadhyay and Danupon Nanongkai. A note on isolating cut lemma for submodular function minimization, 2021. URL: http://arxiv.org/abs/2103.15724.
  44. Hiroshi Nagamochi and Toshihide Ibaraki. A linear-time algorithm for finding a sparse k-connected spanning subgraph of a k-connected graph. Algorithmica, 7(5&6):583-596, 1992. Google Scholar
  45. Danupon Nanongkai, Thatchaphol Saranurak, and Sorrachai Yingchareonthawornchai. Breaking quadratic time for small vertex connectivity and an approximation scheme. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 241-252, 2019. Google Scholar
  46. Kent Quanrud. Fast approximations for rooted connectivity in weighted directed graphs. CoRR, abs/2104.06933, 2021. URL: http://arxiv.org/abs/2104.06933.
  47. Maurice Queyranne. Minimizing symmetric submodular functions. Mathematical Programming, 82(1-2):3-12, 1998. Google Scholar
  48. Alexander Schrijver. Combinatorial Optimization - Polyhedra and Efficiency. Springer, 2003. Google Scholar
  49. Mechthild Stoer and Frank Wagner. A simple min-cut algorithm. Journal of the ACM (JACM), 44(4):585-591, 1997. Google Scholar
  50. Jan van den Brand, Yin Tat Lee, Yang P. Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang. Minimum cost flows, mdps, and 𝓁₁-regression in nearly linear time for dense instances. CoRR, abs/2101.05719, 2021. URL: http://arxiv.org/abs/2101.05719.
  51. Jan van den Brand, Yin Tat Lee, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang. Bipartite matching in nearly-linear time on moderately dense graphs. CoRR, abs/2009.01802, 2020. URL: http://arxiv.org/abs/2009.01802.
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