Document Open Access Logo

Faster Algorithms for Rooted Connectivity in Directed Graphs

Authors Chandra Chekuri, Kent Quanrud

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2021.49.pdf
  • Filesize: 0.95 MB
  • 16 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. Faster Algorithms for Rooted Connectivity in Directed Graphs. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 49:1-49:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ICALP.2021.49

Abstract

We consider the fundamental problems of determining the rooted and global edge and vertex connectivities (and computing the corresponding cuts) in directed graphs. For rooted (and hence also global) edge connectivity with small integer capacities we give a new randomized Monte Carlo algorithm that runs in time Õ(n²). For rooted edge connectivity this is the first algorithm to improve on the Ω(n³) time bound in the dense-graph high-connectivity regime. Our result relies on a simple combination of sampling coupled with sparsification that appears new, and could lead to further tradeoffs for directed graph connectivity problems. We extend the edge connectivity ideas to rooted and global vertex connectivity in directed graphs. We obtain a (1+ε)-approximation for rooted vertex connectivity in Õ(nW/ε) time where W is the total vertex weight (assuming integral vertex weights); in particular this yields an Õ(n²/ε) time randomized algorithm for unweighted graphs. This translates to a Õ(KnW) time exact algorithm where K is the rooted connectivity. We build on this to obtain similar bounds for global vertex connectivity. Our results complement the known results for these problems in the low connectivity regime due to work of Gabow [Harold N. Gabow, 1995] for edge connectivity from 1991, and the very recent work of Nanongkai et al. [Nanongkai et al., 2019] and Forster et al. [Sebastian Forster et al., 2020] for vertex connectivity.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
Keywords
  • rooted connectivity
  • directed graph
  • fast algorithm
  • sparsification

Metrics

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

Related Versions

References

  1. Josh Alman and Virginia Vassilevska Williams. A refined laser method and faster matrix multiplication. In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 522-539. SIAM, 2021. Google Scholar
  2. 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.
  3. Joseph Cheriyan and John H. Reif. Directed s-t numberings, rubber bands, and testing digraph k-vertex connectivity. Comb., 14(4):435-451, 1994. Google Scholar
  4. Jack Edmonds. Submodular functions, matroids, and certain polyhedra. In R. Guy, H. Hanani, N. Sauer, and J. Schönheim, editors, Combinatorial Structures and Their Applications (Proceedings Calgary International Conference on Combinatorial Structures and Their Applications, Calgary, Alberta, 1969; , eds.), pages 69-87. Gordon and Breach, New York, 1970. Google Scholar
  5. Shimon Even and Robert Endre Tarjan. Network flow and testing graph connectivity. SIAM J. Comput., 4(4):507-518, 1975. Google Scholar
  6. 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
  7. András Frank. Connections in Combinatorial Optimization. Oxford University Press, 2011. Google Scholar
  8. Harold N. Gabow. A matroid approach to finding edge connectivity and packing arborescences. J. Comput. Syst. Sci., 50(2):259-273, 1995. Google Scholar
  9. Harold N. Gabow. Using expander graphs to find vertex connectivity. J. ACM, 53(5):800-844, 2006. Google Scholar
  10. Yu Gao, Yang P. Liu, and Richard Peng. Fully dynamic electrical flows: Sparse maxflow faster than goldberg-rao. CoRR, abs/2101.07233, 2021. URL: http://arxiv.org/abs/2101.07233.
  11. Andrew V. Goldberg and Satish Rao. Beyond the flow decomposition barrier. J. ACM, 45(5):783-797, 1998. Google Scholar
  12. 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
  13. 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
  14. 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
  15. 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
  16. Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak, and Sorrachai Yingchareonthawornchai. Vertex connectivity in poly-logarithmic max-flows. To appear in ACM STOC,, 2021. Google Scholar
  17. Jason Li and Debmalya Panigrahi. Deterministic min-cut in poly-logarithmic max-flows. In IEEE 61st Annual Symposium on Foundations of Computer Science, FOCS 2020. IEEE Computer Society, 2020. Google Scholar
  18. 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
  19. Aleksander Madry. Navigating central path with electrical flows: From flows to matchings, and back. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA, pages 253-262. IEEE Computer Society, 2013. Google Scholar
  20. 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
  21. Yishay Mansour and Baruch Schieber. Finding the edge connectivity of directed graphs. J. Algorithms, 10(1):76-85, 1989. Google Scholar
  22. David W. Matula. Determining edge connectivity in o(nm). In 28th Annual Symposium on Foundations of Computer Science, Los Angeles, California, USA, 27-29 October 1987, pages 249-251. IEEE Computer Society, 1987. URL: https://doi.org/10.1109/SFCS.1987.19.
  23. 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
  24. James B. Orlin. Max flows in o(mn) time, or better. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013, pages 765-774. ACM, 2013. Google Scholar
  25. V. D. Podderyugin. An algorithm for finding the edge connectivity of graphs. Vopr. Kibern., 2:136, 1973. Google Scholar
  26. Kent Quanrud. Fast approximations for rooted connectivity in weighted directed graphs. CoRR, abs/2104.06933, 2021. URL: http://arxiv.org/abs/2104.06933.
  27. Alexander Schrijver. Combinatorial Optimization - Polyhedra and Efficiency. Springer, 2003. Google Scholar
  28. 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.
  29. 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