Document Open Access Logo

Minimum+1 (s,t)-cuts and Dual Edge Sensitivity Oracle

Authors Surender Baswana , Koustav Bhanja , Abhyuday Pandey

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2022.15.pdf
  • Filesize: 1.57 MB
  • 20 pages

Document Identifiers

Author Details

Surender Baswana
  • Department of Computer Science and Engineering, Indian Institute of Technology Kanpur, India
Koustav Bhanja
  • Department of Computer Science and Engineering, Indian Institute of Technology Kanpur, India
Abhyuday Pandey
  • Department of Computer Science and Engineering, Indian Institute of Technology Kanpur, India

Cite AsGet BibTex

Surender Baswana, Koustav Bhanja, and Abhyuday Pandey. Minimum+1 (s,t)-cuts and Dual Edge Sensitivity Oracle. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 15:1-15:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ICALP.2022.15

Abstract

Let G be a directed multi-graph on n vertices and m edges with a designated source vertex s and a designated sink vertex t. We study the (s,t)-cuts of capacity minimum+1 and as an important application of them, we give a solution to the dual edge sensitivity for (s,t)-mincuts - reporting the (s,t)-mincut upon failure or addition of any pair of edges. Picard and Queyranne [Mathematical Programming Studies, 13(1):8-16, 1980] showed that there exists a directed acyclic graph (DAG) that compactly stores all minimum (s,t)-cuts of G. This structure also acts as an oracle for the single edge sensitivity of minimum (s,t)-cut. Dinitz and Nutov [STOC, pages 509-518, 1995] showed that there exists an 𝒪(n) size 2-level cactus model that stores all global cuts of capacity minimum+1. However, for minimum+1 (s,t)-cuts, no such compact structures exist till date. We present the following structural and algorithmic results on minimum+1 (s,t)-cuts. 1) There exists a pair of DAGs of size O(m) that compactly store all minimum+1 (s,t)-cuts of G. Each minimum+1 (s,t)-cut appears as a (s,t)-cut in one of the 2 DAGs and is 3-transversal - it intersects any path in the DAG at most thrice. 2) There exists an O(n²) size data structure that, given a pair of vertices {u,v} which are not separated by an (s,t)-mincut, can determine in 𝒪(1) time if there exists a minimum+1 (s,t)-cut, say (A,B), such that {s,u} ∈ A and {v,t} ∈ B; the corresponding cut can be reported in 𝒪(|B|) time. 3) There exists an O(n²) size data structure that solves the dual edge sensitivity problem for (s,t)-mincuts. It takes 𝒪(1) time to report the value of a resulting (s,t)-mincut (A,B) and 𝒪(|B|) time to report the cut. 4) For the data structure problems addressed in (2) and (3) above, we also provide a matching conditional lower bound. We establish a close relationship among three seemingly unrelated problems – all-pairs directed reachability problem, the dual edge sensitivity problem for (s,t)-mincuts, and 2× 2 maximum flow. Assuming the directed reachability hypothesis, this leads to Ω(n²) lower bounds on the space for the latter two problems.

Subject Classification

ACM Subject Classification
  • Theory of computation → Dynamic graph algorithms
  • Theory of computation → Network flows
Keywords
  • mincut
  • maxflow
  • fault tolerant

Metrics

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

Related Versions

References

  1. Surender Baswana and Abhyuday Pandey. Sensitivity oracles for all-pairs mincuts. In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022, pages 581-609. SIAM, 2022. URL: https://doi.org/10.1137/1.9781611977073.27.
  2. András A. Benczúr. A representation of cuts within 6/5 times the edge connectivity with applications. In 36th Annual Symposium on Foundations of Computer Science, Milwaukee, Wisconsin, USA, 23-25 October 1995, pages 92-102. IEEE Computer Society, 1995. URL: https://doi.org/10.1109/SFCS.1995.492466.
  3. Keerti Choudhary. An optimal dual fault tolerant reachability oracle. In Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi, editors, 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, volume 55 of LIPIcs, pages 130:1-130:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.ICALP.2016.130.
  4. Camil Demetrescu, Mikkel Thorup, Rezaul Alam Chowdhury, and Vijaya Ramachandran. Oracles for distances avoiding a failed node or link. SIAM J. Comput., 37(5):1299-1318, 2008. URL: https://doi.org/10.1137/S0097539705429847.
  5. Efim A Dinitz, Alexander V Karzanov, and Michael V Lomonosov. On the structure of the system of minimum edge cuts in a graph. Issledovaniya po Diskretnoi Optimizatsii, pages 290-306, 1976. Google Scholar
  6. Yefim Dinitz. Maintaining the 4-edge-connected components of a graph on-line. In Second Israel Symposium on Theory of Computing Systems, ISTCS 1993, Natanya, Israel, June 7-9, 1993, Proceedings, pages 88-97. IEEE Computer Society, 1993. URL: https://doi.org/10.1109/ISTCS.1993.253480.
  7. Yefim Dinitz and Zeev Nutov. A 2-level cactus model for the system of minimum and minimum+1 edge-cuts in a graph and its incremental maintenance. In Frank Thomson Leighton and Allan Borodin, editors, Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 29 May-1 June 1995, Las Vegas, Nevada, USA, pages 509-518. ACM, 1995. URL: https://doi.org/10.1145/225058.225268.
  8. Yefim Dinitz and Alek Vainshtein. The general structure of edge-connectivity of a vertex subset in a graph and its incremental maintenance. odd case. SIAM J. Comput., 30(3):753-808, 2000. URL: https://doi.org/10.1137/S0097539797330045.
  9. Ran Duan and Seth Pettie. Dual-failure distance and connectivity oracles. In Claire Mathieu, editor, Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, New York, NY, USA, January 4-6, 2009, pages 506-515. SIAM, 2009. URL: http://dl.acm.org/citation.cfm?id=1496770.1496826.
  10. L. R. Ford and D. R. Fulkerson. Maximal flow through a network. Canadian Journal of Mathematics, 8:399-404, 1956. URL: https://doi.org/10.4153/CJM-1956-045-5.
  11. Harold N. Gabow. Efficient splitting off algorithms for graphs. In Frank Thomson Leighton and Michael T. Goodrich, editors, Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 23-25 May 1994, Montréal, Québec, Canada, pages 696-705. ACM, 1994. URL: https://doi.org/10.1145/195058.195436.
  12. Zvi Galil and Giuseppe F. Italiano. Maintaining the 3-edge-connected components of a graph on-line. SIAM J. Comput., 22(1):11-28, 1993. URL: https://doi.org/10.1137/0222002.
  13. Naveen Garg and Vijay V. Vazirani. A polyhedron with alls - t cuts as vertices, and adjacency of cuts. Math. Program., 70:17-25, 1995. URL: https://doi.org/10.1007/BF01585926.
  14. Isaac Goldstein, Tsvi Kopelowitz, Moshe Lewenstein, and Ely Porat. Conditional lower bounds for space/time tradeoffs. In Faith Ellen, Antonina Kolokolova, and Jörg-Rüdiger Sack, editors, Algorithms and Data Structures - 15th International Symposium, WADS 2017, St. John’s, NL, Canada, July 31 - August 2, 2017, Proceedings, volume 10389 of Lecture Notes in Computer Science, pages 421-436. Springer, 2017. URL: https://doi.org/10.1007/978-3-319-62127-2_36.
  15. Ken-ichi Kawarabayashi and Mikkel Thorup. Deterministic edge connectivity in near-linear time. J. ACM, 66(1):4:1-4:50, 2019. URL: https://doi.org/10.1145/3274663.
  16. Yin Tat Lee and Aaron Sidford. Path finding methods for linear programming: Solving linear programs in õ(vrank) 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. URL: https://doi.org/10.1109/FOCS.2014.52.
  17. Thomas Lengauer and Robert Endre Tarjan. A fast algorithm for finding dominators in a flowgraph. ACM Trans. Program. Lang. Syst., 1(1):121-141, 1979. URL: https://doi.org/10.1145/357062.357071.
  18. Jason Li. Deterministic mincut in almost-linear time. In Samir Khuller and Virginia Vassilevska Williams, editors, STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 384-395. ACM, 2021. URL: https://doi.org/10.1145/3406325.3451114.
  19. Jason Li and Debmalya Panigrahi. Deterministic min-cut in poly-logarithmic max-flows. In Sandy Irani, editor, 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 85-92. IEEE, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00017.
  20. Merav Parter. Dual failure resilient BFS structure. In Chryssis Georgiou and Paul G. Spirakis, editors, Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC 2015, Donostia-San Sebastián, Spain, July 21 - 23, 2015, pages 481-490. ACM, 2015. URL: https://doi.org/10.1145/2767386.2767408.
  21. Merav Parter and David Peleg. Sparse fault-tolerant BFS structures. ACM Trans. Algorithms, 13(1):11:1-11:24, 2016. URL: https://doi.org/10.1145/2976741.
  22. Mihai Patrascu. Unifying the landscape of cell-probe lower bounds. SIAM J. Comput., 40(3):827-847, 2011. URL: https://doi.org/10.1137/09075336X.
  23. Jean-Claude Picard and Maurice Queyranne. On the structure of all minimum cuts in a network and applications. In Rayward-Smith V.J. (eds) Combinatorial Optimization II. Mathematical Programming Studies, 13(1):8-16, 1980. URL: https://doi.org/10.1007/BFb0120902.
  24. Vijay V. Vazirani and Mihalis Yannakakis. Suboptimal cuts: Their enumeration, weight and number (extended abstract). In Werner Kuich, editor, Automata, Languages and Programming, 19th International Colloquium, ICALP92, Vienna, Austria, July 13-17, 1992, Proceedings, volume 623 of Lecture Notes in Computer Science, pages 366-377. Springer, 1992. URL: https://doi.org/10.1007/3-540-55719-9_88.
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