Document Open Access Logo

Determining 4-Edge-Connected Components in Linear Time

Authors Wojciech Nadara, Mateusz Radecki, Marcin Smulewicz, Marek Sokołowski

PDF
Thumbnail PDF

File

LIPIcs.ESA.2021.71.pdf
  • Filesize: 0.64 MB
  • 15 pages

Document Identifiers

Author Details

Wojciech Nadara
  • Institute of Informatics, University of Warsaw, Poland
Mateusz Radecki
  • University of Warsaw, Poland
Marcin Smulewicz
  • Institute of Informatics, University of Warsaw, Poland
Marek Sokołowski
  • Institute of Informatics, University of Warsaw, Poland

Funding

  • Nadara, Wojciech: Supported by ERC Starting Grant CUTACOMBS (Grant Agreement No 714704).
  • Smulewicz, Marcin: Supported by ERC Starting Grant TOTAL (Grant Agreement No 677651).
  • Sokołowski, Marek: Supported by ERC Starting Grant BOBR (Grant Agreement No 948057).

Cite AsGet BibTex

Wojciech Nadara, Mateusz Radecki, Marcin Smulewicz, and Marek Sokołowski. Determining 4-Edge-Connected Components in Linear Time. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 71:1-71:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ESA.2021.71

Abstract

In this work, we present the first linear time deterministic algorithm computing the 4-edge-connected components of an undirected graph. First, we show an algorithm listing all 3-edge-cuts in a given 3-edge-connected graph, and then we use the output of this algorithm in order to determine the 4-edge-connected components of the graph.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
Keywords
  • graphs
  • connectivity
  • cuts

Metrics

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

Related Versions

References

  1. Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. Analyzing Graph Structure via Linear Measurements. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '12, page 459–467, USA, 2012. Society for Industrial and Applied Mathematics. URL: https://doi.org/10.1137/1.9781611973099.40.
  2. Nalin Bhardwaj, Antonio Molina Lovett, and Bryce Sandlund. A Simple Algorithm for Minimum Cuts in Near-Linear Time. In Susanne Albers, editor, 17th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2020, June 22-24, 2020, Tórshavn, Faroe Islands, volume 162 of LIPIcs, pages 12:1-12:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.SWAT.2020.12.
  3. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, 3rd Edition. MIT Press, 2009. URL: http://mitpress.mit.edu/books/introduction-algorithms.
  4. Giuseppe Di Battista and Roberto Tamassia. On-Line Graph Algorithms with SPQR-Trees. In Michael S. Paterson, editor, Automata, Languages and Programming, pages 598-611, Berlin, Heidelberg, 1990. Springer Berlin Heidelberg. Google Scholar
  5. Yefim Dinitz, Alexander V. Karzanov, and Michael V. Lomonosov. On the structure of a family of minimum weighted cuts in a graph. Studies in Discrete Optimization, page 290–306, 1976. Google Scholar
  6. Yefim Dinitz and Jeffery R. Westbrook. Maintaining the Classes of 4-Edge-Connectivity in a Graph On-Line. Algorithmica, 20(3):242-276, March 1998. URL: https://doi.org/10.1007/PL00009195.
  7. David Eppstein, Zvi Galil, Giuseppe F. Italiano, and Amnon Nissenzweig. Sparsification—a technique for speeding up dynamic graph algorithms. J. ACM, 44(5):669–696, 1997. URL: https://doi.org/10.1145/265910.265914.
  8. Tamás Fleiner and András Frank. A quick proof for the cactus representation of mincuts. Technical Report QP-2009-03, Egerváry Research Group, Budapest, 2009. Google Scholar
  9. Greg N. Frederickson. Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications. SIAM Journal on Computing, 14(4):781-798, 1985. URL: https://doi.org/10.1137/0214055.
  10. Harold N. Gabow and Robert Endre Tarjan. A Linear-Time Algorithm for a Special Case of Disjoint Set Union. J. Comput. Syst. Sci., 30(2):209-221, 1985. URL: https://doi.org/10.1016/0022-0000(85)90014-5.
  11. Zvi Galil and Giuseppe F. Italiano. Fully Dynamic Algorithms for Edge Connectivity Problems. In Proceedings of the Twenty-Third Annual ACM Symposium on Theory of Computing, STOC '91, page 317–327, New York, NY, USA, 1991. Association for Computing Machinery. URL: https://doi.org/10.1145/103418.103454.
  12. Zvi Galil and Giuseppe F. Italiano. Reducing edge connectivity to vertex connectivity. SIGACT News, 22(1):57–61, 1991. URL: https://doi.org/10.1145/122413.122416.
  13. Ralph E. Gomory and T. C. Hu. Multi-Terminal Network Flows. Journal of the Society for Industrial and Applied Mathematics, 9(4):551-570, 1961. URL: http://www.jstor.org/stable/2098881.
  14. Dov Harel and Robert Endre Tarjan. Fast Algorithms for Finding Nearest Common Ancestors. SIAM J. Comput., 13(2):338-355, 1984. URL: https://doi.org/10.1137/0213024.
  15. Ramesh Hariharan, Telikepalli Kavitha, and Debmalya Panigrahi. Efficient Algorithms for Computing All Low s-t Edge Connectivities and Related Problems. In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '07, page 127–136, USA, 2007. Society for Industrial and Applied Mathematics. Google Scholar
  16. Monika Henzinger, Satish Rao, and Di Wang. Local Flow Partitioning for Faster Edge Connectivity, pages 1919-1938. Society for Industrial and Applied Mathematics, 2017. URL: https://doi.org/10.1137/1.9781611974782.125.
  17. Monika Rauch Henzinger. Fully dynamic biconnectivity in graphs. Algorithmica, 13(6):503-538, June 1995. URL: https://doi.org/10.1007/BF01189067.
  18. Monika Rauch Henzinger and Valerie King. Randomized Dynamic Graph Algorithms with Polylogarithmic Time per Operation. In Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, STOC '95, page 519–527, New York, NY, USA, 1995. Association for Computing Machinery. URL: https://doi.org/10.1145/225058.225269.
  19. Monika Rauch Henzinger and Mikkel Thorup. Sampling to Provide or to Bound: With Applications to Fully Dynamic Graph Algorithms. Random Struct. Algorithms, 11(4):369–379, 1997. Google Scholar
  20. Jacob Holm, Kristian de Lichtenberg, and Mikkel Thorup. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM, 48(4):723–760, 2001. URL: https://doi.org/10.1145/502090.502095.
  21. Jacob Holm and Eva Rotenberg. Worst-Case Polylog Incremental SPQR-Trees: Embeddings, Planarity, and Triconnectivity. In Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '20, page 2378–2397, USA, 2020. Society for Industrial and Applied Mathematics. Google Scholar
  22. Jacob Holm, Eva Rotenberg, and Mikkel Thorup. Dynamic Bridge-Finding in Õ(log² n) Amortized Time. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '18, page 35–52, USA, 2018. Society for Industrial and Applied Mathematics. Google Scholar
  23. John Hopcroft and Robert Tarjan. Algorithm 447: Efficient Algorithms for Graph Manipulation. Commun. ACM, 16(6):372–378, 1973. URL: https://doi.org/10.1145/362248.362272.
  24. John Hopcroft and Robert Tarjan. Dividing a Graph into Triconnected Components. SIAM Journal on Computing, 2(3):135-158, 1973. URL: https://doi.org/10.1137/0202012.
  25. Shang-En Huang, Dawei Huang, Tsvi Kopelowitz, and Seth Pettie. Fully Dynamic Connectivity in O(log n (log log n)²) Amortized Expected Time. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '17, page 510–520, USA, 2017. Society for Industrial and Applied Mathematics. Google Scholar
  26. Arkady Kanevsky, Roberto Tamassia, Giuseppe Di Battista, and Jianer Chen. On-Line Maintenance of the Four-Connected Components of a Graph. In 32nd Annual Symposium on Foundations of Computer Science, San Juan, Puerto Rico, 1-4 October 1991, pages 793-801, 1991. URL: https://doi.org/10.1109/SFCS.1991.185451.
  27. Bruce M. Kapron, Valerie King, and Ben Mountjoy. Dynamic graph connectivity in polylogarithmic worst case time. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '13, page 1131–1142, USA, 2013. Society for Industrial and Applied Mathematics. Google Scholar
  28. Bruce M. Kapron, Valerie King, and Ben Mountjoy. Dynamic graph connectivity in polylogarithmic worst case time. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '13, page 1131–1142, USA, 2013. Society for Industrial and Applied Mathematics. URL: https://doi.org/10.1137/1.9781611973105.81.
  29. David R. Karger. Minimum Cuts in Near-Linear Time. J. ACM, 47(1):46–76, 2000. URL: https://doi.org/10.1145/331605.331608.
  30. Kenichi Kawarabayashi and Mikkel Thorup. Deterministic Global Minimum Cut of a Simple Graph in Near-Linear Time. In Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, STOC '15, page 665–674, New York, NY, USA, 2015. Association for Computing Machinery. URL: https://doi.org/10.1145/2746539.2746588.
  31. Johannes A. La Poutré and Jeffery Westbrook. Dynamic 2-Connectivity with Backtracking. SIAM J. Comput., 28(1):10–26, 1999. URL: https://doi.org/10.1137/S0097539794272582.
  32. Johannes A. La Poutré, Jan van Leeuwen, and Mark H. Overmars. Maintenance of 2- and 3-edge-connected components of graphs I. Discrete Mathematics, 114(1):329-359, 1993. URL: https://doi.org/10.1016/0012-365X(93)90376-5.
  33. Wojciech Nadara, Mateusz Radecki, Marcin Smulewicz, and Marek Sokołowski. Determining 4-edge-connected components in linear time. CoRR, abs/2105.01699, 2021. URL: http://arxiv.org/abs/2105.01699.
  34. Hiroshi Nagamochi and Toshihide Ibaraki. A linear time algorithm for computing 3-edge-connected components in a multigraph. Japan Journal of Industrial and Applied Mathematics, 9(2):163, June 1992. URL: https://doi.org/10.1007/BF03167564.
  35. Nima Norouzi and Yung H. Tsin. A simple 3-edge connected component algorithm revisited. Information Processing Letters, 114(1):50-55, 2014. URL: https://doi.org/10.1016/j.ipl.2013.09.010.
  36. Richard Peng, Bryce Sandlund, and Daniel Dominic Sleator. Optimal Offline Dynamic 2, 3-Edge/Vertex Connectivity. In Zachary Friggstad, Jörg-Rüdiger Sack, and Mohammad R. Salavatipour, editors, Algorithms and Data Structures - 16th International Symposium, WADS 2019, Edmonton, AB, Canada, August 5-7, 2019, Proceedings, volume 11646 of Lecture Notes in Computer Science, pages 553-565. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-24766-9_40.
  37. Seth Pettie and Longhui Yin. The Structure of Minimum Vertex Cuts, 2021. URL: http://arxiv.org/abs/2102.06805.
  38. Robert E. Tarjan and Jan van Leeuwen. Worst-Case Analysis of Set Union Algorithms. J. ACM, 31(2):245–281, March 1984. URL: https://doi.org/10.1145/62.2160.
  39. Robert Endre Tarjan. Depth-First Search and Linear Graph Algorithms. SIAM J. Comput., 1(2):146-160, 1972. URL: https://doi.org/10.1137/0201010.
  40. Mikkel Thorup. Near-optimal fully-dynamic graph connectivity. In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, STOC '00, page 343–350, New York, NY, USA, 2000. Association for Computing Machinery. URL: https://doi.org/10.1145/335305.335345.
  41. Yung H. Tsin. A Simple 3-Edge-Connected Component Algorithm. Theory of Computing Systems, 40(2):125-142, February 2007. URL: https://doi.org/10.1007/s00224-005-1269-4.
  42. Yung H. Tsin. Yet another optimal algorithm for 3-edge-connectivity. Journal of Discrete Algorithms, 7(1):130-146, 2009. Selected papers from the 1st International Workshop on Similarity Search and Applications (SISAP). URL: https://doi.org/10.1016/j.jda.2008.04.003.
  43. Jeffery Westbrook and Robert E. Tarjan. Maintaining bridge-connected and biconnected components on-line. Algorithmica, 7(1):433-464, June 1992. URL: https://doi.org/10.1007/BF01758773.
  44. Christian Wulff-Nilsen. Faster Deterministic Fully-Dynamic Graph Connectivity. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '13, page 1757–1769, USA, 2013. Society for Industrial and Applied Mathematics. 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