Document Open Access Logo

The Structure of Minimum Vertex Cuts

Authors Seth Pettie, Longhui Yin

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2021.105.pdf
  • Filesize: 1.22 MB
  • 20 pages

Document Identifiers

Author Details

Seth Pettie
  • University of Michigan, Ann Arbor, MI, USA
Longhui Yin
  • Tsinghua University, Beijing, China

Funding

  • Pettie, Seth: This work was supported by NSF grants CCF-1637546 and CCF-1815316.
  • Yin, Longhui: Supported by a grant from Tsinghua University.

Cite AsGet BibTex

Seth Pettie and Longhui Yin. The Structure of Minimum Vertex Cuts. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 105:1-105:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ICALP.2021.105

Abstract

In this paper we continue a long line of work on representing the cut structure of graphs. We classify the types of minimum vertex cuts, and the possible relationships between multiple minimum vertex cuts. As a consequence of these investigations, we exhibit a simple O(κ n)-space data structure that can quickly answer pairwise (κ+1)-connectivity queries in a κ-connected graph. We also show how to compute the "closest" κ-cut to every vertex in near linear Õ(m+poly(κ)n) time.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Paths and connectivity problems
  • Theory of computation → Data structures design and analysis
Keywords
  • Graph theory
  • vertex connectivity
  • data structures

Metrics

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

Related Versions

References

  1. Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi. Cut-equivalent trees are optimal for min-cut queries. In Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 105-118, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00019.
  2. S. Baswana, K. Choudhary, and L. Roditty. Fault tolerant subgraph for single source reachability: generic and optimal. In Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC), pages 509-518, 2016. URL: https://doi.org/10.1145/2897518.2897648.
  3. Joshua D. Batson, Daniel A. Spielman, and Nikhil Srivastava. Twice-Ramanujan sparsifiers. SIAM J. Comput., 41(6):1704-1721, 2012. URL: https://doi.org/10.1137/090772873.
  4. G. Di Battista and R. Tamassia. On-line maintenance of triconnected components with SPQR-trees. Algorithmica, 15:302-318, 1996. Google Scholar
  5. Giuseppe Di Battista and Roberto Tamassia. Incremental planarity testing (extended abstract). In Proceedings of the 30th Annual Symposium on Foundations of Computer Science (FOCS), pages 436-441, 1989. URL: https://doi.org/10.1109/SFCS.1989.63515.
  6. A. A. Benczúr. Counterexamples for directed and node capacitated cut-trees. SIAM J. Comput., 24(3):505-510, 1995. Google Scholar
  7. A. A. Benczúr and M. X. Goemans. Deformable polygon representation and near-mincuts. In M. Grötschel and G. O. H. Katona, editors, Building Bridges: Between Mathematics and Computer Science, volume 19 of Bolyai Society Mathematical Studies, pages 103-135. Springer, 2008. Google Scholar
  8. András A. Benczúr and David R. Karger. Randomized approximation schemes for cuts and flows in capacitated graphs. SIAM J. Comput., 44(2):290-319, 2015. URL: https://doi.org/10.1137/070705970.
  9. Chung-Kuan Cheng and T. C. Hu. Ancestor tree for arbitrary multi-terminal cut functions. Ann. Oper. Res., 33(3):199-213, 1991. URL: https://doi.org/10.1007/BF02115755.
  10. K. Choudhary. An optimal dual fault tolerant reachability oracle. In Proceedings 43rd Int'l Colloq. on Automata, Languages, and Programming (ICALP), 2016. Google Scholar
  11. Robert F Cohen, Giuseppe Di Battista, Arkady Kanevsky, and Roberto Tamassia. Reinventing the wheel: an optimal data structure for connectivity queries (extended abstract). In Proceedings of the 25th Annual ACM Symposium on Theory of Computing (STOC), pages 194-200, 1993. Google Scholar
  12. William H. Cunningham and Jack Edmonds. A combinatorial decomposition theory. Canadian J. Math., 32(3):734-765, 1980. URL: https://doi.org/10.4153/CJM-1980-057-7.
  13. E. A. Dinic, A. V. Karzanov, and M. V. Lomonosov. On the structure of the system of minimum edge cuts in a graph. Studies in Discrete Optimization, pages 290-306, 1976. (in Russian). Google Scholar
  14. Y. Dinitz and Z. Nutov. A 2-level cactus model for the system of minimum and minimum+1 edge-cuts in a graph and its incremental maintenance. In Proceedings 27th ACM Symposium on Theory of Computing (STOC), pages 509-518, 1995. Google Scholar
  15. Y. Dinitz and Z. Nutov. A 2-level cactus tree model for the system of minimum and minimum+1 edge cuts of a graph and its incremental maintenance. Part I: the odd case. Unpublished manuscript, 1999. Google Scholar
  16. Y. Dinitz and Z. Nutov. A 2-level cactus tree model for the system of minimum and minimum+1 edge cuts of a graph and its incremental maintenance. Part II: the even case. Unpublished manuscript, 1999. Google Scholar
  17. Yefim Dinitz and Alek Vainshtein. The connectivity carcass of a vertex subset in a graph and its incremental maintenance. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing (STOC), pages 716-725, 1994. URL: https://doi.org/10.1145/195058.195442.
  18. Yefim Dinitz and Alek Vainshtein. Locally orientable graphs, cell structures, and a new algorithm for the incremental maintenance of connectivity carcasses. In Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 302-311, 1995. URL: http://dl.acm.org/citation.cfm?id=313651.313711.
  19. 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.
  20. R. Duan and S. Pettie. Connectivity oracles for failure prone graphs. In Proceedings 42nd ACM Symposium on Theory of Computing, pages 465-474, 2010. Google Scholar
  21. R. Duan and S. Pettie. Connectivity oracles in graphs subject to vertex failures. SIAM J. Comput., 49(6):1363-1396, 2020. Google Scholar
  22. Donatella Firmani, Loukas Georgiadis, Giuseppe F. Italiano, Luigi Laura, and Federico Santaroni. Strong articulation points and strong bridges in large scale graphs. Algorithmica, 74(3):1123-1147, 2016. URL: https://doi.org/10.1007/s00453-015-9991-z.
  23. 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 Proceedings of the 31st ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2046-2065. SIAM, 2020. URL: https://doi.org/10.1137/1.9781611975994.126.
  24. András Frank and Tibor Jordán. Minimal edge-coverings of pairs of sets. J. Comb. Theory, Ser. B, 65(1):73-110, 1995. URL: https://doi.org/10.1006/jctb.1995.1044.
  25. Harold N Gabow. A representation for crossing set families with applications to submodular flow problems. In Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, pages 202-211, 1993. Google Scholar
  26. Harold N. Gabow. Using expander graphs to find vertex connectivity. J. ACM, 53(5):800-844, 2006. URL: https://doi.org/10.1145/1183907.1183912.
  27. Yu Gao, Jason Li, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak, and Sorrachai Yingchareonthawornchai. Deterministic graph cuts in subquadratic time: Sparse, balanced, and k-vertex. CoRR, abs/1910.07950, 2019. URL: http://arxiv.org/abs/1910.07950.
  28. Loukas Georgiadis, Giuseppe F. Italiano, Luigi Laura, and Nikos Parotsidis. 2-edge connectivity in directed graphs. ACM Trans. Algorithms, 13(1):9:1-9:24, 2016. URL: https://doi.org/10.1145/2968448.
  29. Loukas Georgiadis, Giuseppe F. Italiano, Luigi Laura, and Nikos Parotsidis. 2-vertex connectivity in directed graphs. Inf. Comput., 261:248-264, 2018. URL: https://doi.org/10.1016/j.ic.2018.02.007.
  30. Loukas Georgiadis, Giuseppe F. Italiano, and Nikos Parotsidis. Strong connectivity in directed graphs under failures, with applications. SIAM J. Comput., 49(5):865-926, 2020. URL: https://doi.org/10.1137/19M1258530.
  31. R. E. Gomory and T. C. Hu. Multi-terminal network flows. Journal of the Society for Industrial and Applied Mathematics, 9, 1961. Google Scholar
  32. Frieda Granot and Refael Hassin. Multi-terminal maximum flows in node-capacitated networks. Discrete applied mathematics, 13(2-3):157-163, 1986. Google Scholar
  33. D. Gusfield and D. Naor. Efficient algorithms for generalized cut trees. In Proceedings First ACM-SIAM Symposium on Discrete Algorithms, pages 422-433, 1990. Google Scholar
  34. Dan Gusfield and Dalit Naor. Extracting maximal information about sets of minimum cuts. Algorithmica, 10(1):64-89, 1993. Google Scholar
  35. Refael Hassin and Asaf Levin. Flow trees for vertex-capacitated networks. Discrete applied mathematics, 155(4):572-578, 2007. Google Scholar
  36. J. E. Hopcroft and R. E. Tarjan. Dividing a graph into triconnected components. SIAM J. Comput., 2(3):135-158, 1973. Google Scholar
  37. Tai-Hsin Hsu and Hsueh-I Lu. An optimal labeling for node connectivity. In Proceedings of the 20th International Symposium on Algorithms and Computation (ISAAC), pages 303-310. Springer, 2009. Google Scholar
  38. Rani Izsak and Zeev Nutov. A note on labeling schemes for graph connectivity. Information processing letters, 112(1-2):39-43, 2012. Google Scholar
  39. Bill Jackson and Tibor Jordán. Independence free graphs and vertex connectivity augmentation. Journal of Combinatorial Theory, Series B, 94(1):31-77, 2005. Google Scholar
  40. Tibor Jordán. On the optimal vertex-connectivity augmentation. Journal of Combinatorial Theory, Series B, 63(1):8-20, 1995. Google Scholar
  41. Tibor Jordán. On the number of shredders. Journal of Graph Theory, 31(3):195-200, 1999. Google Scholar
  42. A. Kanevsky, R. Tamassia, G. Di Battista, and J. Chen. On-line maintenance of the four-connected components of a graph. In Proceedings 32nd IEEE Symposium on Foundations of Computer Science (FOCS), pages 793-801, 1991. Google Scholar
  43. B. M. Kapron, V. King, and B. Mountjoy. Dynamic graph connectivity in polylogarithmic worst case time. In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1131-1142, 2013. Google Scholar
  44. Michal Katz, Nir A Katz, Amos Korman, and David Peleg. Labeling schemes for flow and connectivity. SIAM J. Comput., 34(1):23-40, 2004. Google Scholar
  45. A. Korman. Labeling schemes for vertex connectivity. ACM Trans. on Algorithms, 6(2), 2010. Google Scholar
  46. Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak, and Sorrachai Yingchareonthawornchai. Vertex connectivity in poly-logarithmic max-flows. In Proceedings of the 53rd ACM Symposium on Theory of Computing (STOC), 2021. Google Scholar
  47. Gilad Liberman and Zeev Nutov. On shredders and vertex connectivity augmentation. Journal of Discrete Algorithms, 5(1):91-101, 2007. Google Scholar
  48. Saunders Mac Lane. A structural characterization of planar combinatorial graphs. Duke Math. J., 3(3):460-472, 1937. URL: https://doi.org/10.1215/S0012-7094-37-00336-3.
  49. Karl Menger. Zur allgemeinen kurventheorie. Fundamenta Mathematicae, 10:96-115, 1927. Google Scholar
  50. H. Nagamochi and T. 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
  51. Zeev Nutov. Approximating connectivity augmentation problems. ACM Trans. Algorithms, 6(1):5:1-5:19, 2009. URL: https://doi.org/10.1145/1644015.1644020.
  52. Zeev Nutov. Improved approximation algorithms for minimum cost node-connectivity augmentation problems. Theory Comput. Syst., 62(3):510-532, 2018. URL: https://doi.org/10.1007/s00224-017-9786-5.
  53. Zeev Nutov and Masao Tsugaki. On (t, k)-shredders in k-connected graphs. Ars Comb., 83, 2007. Google Scholar
  54. M. Pǎtraşcu and M. Thorup. Planning for fast connectivity updates. In Proceedings 48th IEEE Symposium on Foundations of Computer Science (FOCS), pages 263-271, 2007. Google Scholar
  55. Seth Pettie and Longhui Yin. The structure of minimum vertex cuts. CoRR, abs/2102.06805, 2021. URL: http://arxiv.org/abs/2102.06805.
  56. J.-C. Picard and M. Queyranne. On the structure of all minimum cuts in a network and applications. In Combinatorial Optimization II, volume 13 of Mathematical Programming Studies, pages 8-16. Springer, 1980. Google Scholar
  57. C.-P. Schnorr. Bottlenecks and edge connectivity in unsymmetrical networks. SIAM J. Comput., 8(2):265-274, 1979. Google Scholar
  58. R. E. Tarjan. Depth-first search and linear graph algorithms. SIAM J. Comput., 1(2):146-160, 1972. Google Scholar
  59. W. T. Tutte. A theory of 3-connected graphs. Nederl. Akad. Wetensch. Proc. Ser. A 64 = Indag. Math., 23:441-455, 1961. Google Scholar
  60. W. T. Tutte. Connectivity in Graphs. University of Toronto Press, 1966. Google Scholar
  61. H. Whitney. Congruent graphs and the connectivity of graphs. American J. Mathematics, 54(1):150-168, 1932. URL: https://doi.org/10.2307/2371086.
  62. Hassler Whitney. Non-separable and planar graphs. Trans. Amer. Math. Soc., 34(2):339-362, 1932. URL: https://doi.org/10.2307/1989545.
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