Document Open Access Logo

Finding All Global Minimum Cuts in Practice

Authors Monika Henzinger , Alexander Noe , Christian Schulz , Darren Strash

PDF
Thumbnail PDF

File

LIPIcs.ESA.2020.59.pdf
  • Filesize: 0.66 MB
  • 20 pages

Document Identifiers

Author Details

Monika Henzinger
  • University of Vienna, Faculty of Computer Science, Austria
Alexander Noe
  • University of Vienna, Faculty of Computer Science, Austria
Christian Schulz
  • University of Vienna, Faculty of Computer Science, Austria
Darren Strash
  • Hamilton College, Department of Computer Science, Clinton, NY, USA

Funding

The research leading to these results has received funding from the European Research Council under the European Community’s Seventh Framework Programme (FP7/2007-2013) /ERC grant agreement No. 340506. Partially supported by DFG grant SCHU 2567/1-2.

Cite AsGet BibTex

Monika Henzinger, Alexander Noe, Christian Schulz, and Darren Strash. Finding All Global Minimum Cuts in Practice. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 59:1-59:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ESA.2020.59

Abstract

We present a practically efficient algorithm that finds all global minimum cuts in huge undirected graphs. Our algorithm uses a multitude of kernelization rules to reduce the graph to a small equivalent instance and then finds all minimum cuts using an optimized version of the algorithm of Nagamochi, Nakao and Ibaraki. In shared memory we are able to find all minimum cuts of graphs with up to billions of edges and millions of minimum cuts in a few minutes. We also give a new linear time algorithm to find the most balanced minimum cuts given as input the representation of all minimum cuts.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Paths and connectivity problems
  • Mathematics of computing → Graph algorithms
  • Mathematics of computing → Network flows
Keywords
  • Minimum Cut
  • Graph Algorithm
  • Algorithm Engineering
  • Cut Enumeration
  • Balanced Cut
  • Global Minimum Cut
  • Large-scale Graph Analysis

Metrics

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

Supplementary Materials

References

  1. Faisal N. Abu-Khzam, Shaowei Cai, Judith Egan, Peter Shaw, and Kai Wang. Turbo-charging dominating set with an FPT subroutine: Further improvements and experimental analysis. In Proc. 14th Annual Conference on Theory and Applications of Models of Computation (TAMC 2017), volume 10185 of LNCS, pages 59-70. Springer, 2017. URL: https://doi.org/10.1007/978-3-319-55911-7_5.
  2. Takuya Akiba and Yoichi Iwata. Branch-and-reduce exponential/FPT algorithms in practice: A case study of vertex cover. Theor. Comput. Sci., 609, Part 1:211-225, 2016. URL: https://doi.org/10.1016/j.tcs.2015.09.023.
  3. Takuya Akiba, Yoichi Iwata, Yosuke Sameshima, Naoto Mizuno, and Yosuke Yano. Cut tree construction from massive graphs. In Proc. 16th International Conference on Data Mining (ICDM 2016), pages 775-780, 2016. URL: https://doi.org/10.1109/ICDM.2016.0089.
  4. Reid Andersen and Kevin J Lang. An algorithm for improving graph partitions. In Proc. 19th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 651-660. SIAM, 2008. URL: https://dl.acm.org/doi/10.5555/1347082.1347154.
  5. Richard J Anderson and Heather Woll. Wait-free parallel algorithms for the union-find problem. In Proc. 23rd ACM Symposium on Theory of Computing, STOC '91, pages 370-380. ACM, 1991. URL: https://doi.org/10.1145/103418.103458.
  6. David A Bader, Henning Meyerhenke, Peter Sanders, Christian Schulz, Andrea Kappes, and Dorothea Wagner. Benchmarking for graph clustering and partitioning. Encyclopedia of Social Network Analysis and Mining, pages 73-82, 2014. URL: https://doi.org/10.1007/978-1-4614-7163-9_23-1.
  7. Max Bannach and Sebastian Berndt. Practical access to dynamic programming on tree decompositions. In Proc. 26th European Symposium on Algorithms (ESA'18), volume 112 of LIPIcs, pages 6:1-6:13. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.ESA.2018.6.
  8. Sebastian Böcker, Sebastian Briesemeister, and Gunnar W. Klau. Exact algorithms for cluster editing: Evaluation and experiments. Algorithmica, 60(2):316-334, 2011. URL: https://doi.org/10.1007/s00453-009-9339-7.
  9. Paul Bonsma. Most balanced minimum cuts. Discrete Appl. Math., 158(4):261-276, February 2010. URL: https://doi.org/10.1016/j.dam.2009.09.010.
  10. Deng Cai, Zheng Shao, Xiaofei He, Xifeng Yan, and Jiawei Han. Mining hidden community in heterogeneous social networks. In Proc. 3rd International Workshop on Link Discovery (LinkKDD '05), pages 58-65. ACM, 2005. URL: https://doi.org/10.1145/1134271.1134280.
  11. Lijun Chang, Wei Li, and Wenjie Zhang. Computing a near-maximum independent set in linear time by reducing-peeling. In Proc. 2017 ACM International Conference on Management of Data (SIGMOD '17), pages 1181-1196. ACM, 2017. URL: https://doi.org/10.1145/3035918.3035939.
  12. Chandra S. Chekuri, Andrew V. Goldberg, David R. Karger, Matthew S. Levine, and Cliff Stein. Experimental study of minimum cut algorithms. In Proc. 8th Symposium on Discrete Algorithms (SODA '97), pages 324-333. SIAM, 1997. URL: https://dl.acm.org/doi/10.5555/314161.314315.
  13. Leonardo Dagum and Ramesh Menon. OpenMP: An industry standard API for shared-memory programming. IEEE Computational Science and Engineering, 5(1):46-55, 1998. URL: https://doi.org/10.1109/99.660313.
  14. Jakob Dahlum, Sebastian Lamm, Peter Sanders, Christian Schulz, Darren Strash, and Renato F. Werneck. Accelerating local search for the maximum independent set problem. In Proc. 15th International Symposium on Experimental Algorithms (SEA 2016), volume 9685 of LNCS, pages 118-133. Springer, 2016. URL: https://doi.org/10.1007/978-3-319-38851-9_9.
  15. Timothy A Davis and Yifan Hu. The University of Florida sparse matrix collection. ACM Trans. Mathematical Software (TOMS), 38(1):1, 2011. URL: https://doi.org/10.1145/2049662.2049663.
  16. Chris HQ Ding, Xiaofeng He, Hongyuan Zha, Ming Gu, and Horst D Simon. A min-max cut algorithm for graph partitioning and data clustering. In Proc. 2001 IEEE International Conference on Data Mining (ICDM 2001), pages 107-114. IEEE, 2001. URL: https://doi.org/10.1109/ICDM.2001.989507.
  17. Damir Ferizovic, Demian Hespe, Sebastian Lamm, Matthias Mnich, Christian Schulz, and Darren Strash. Engineering kernelization for maximum cut. In Proc. 22nd Symposium on Algorithm Engineering and Experiments (ALENEX 2020), pages 27-41. SIAM, 2020. URL: https://doi.org/10.1137/1.9781611976007.3.
  18. Rudolf Fleischer, Xi Wu, and Liwei Yuan. Experimental study of FPT algorithms for the directed feedback vertex set problem. In Proc. 17th European Symposium on Algorithms (ESA 2009), volume 5757 of LNCS, pages 611-622. Springer, 2009. URL: https://doi.org/10.1007/978-3-642-04128-0_55.
  19. Harold N Gabow. Applications of a poset representation to edge connectivity and graph rigidity. In Proc. 32nd Symposium of Foundations of Computer Science (FOCS '91), pages 812-821. IEEE, 1991. URL: https://doi.org/10.1109/SFCS.1991.185453.
  20. Mohsen Ghaffari, Krzysztof Nowicki, and Mikkel Thorup. Faster algorithms for edge connectivity via random 2-out contractions. In Proc. 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA 2020), pages 1260-1279. SIAM, 2020. URL: https://doi.org/10.1137/1.9781611975994.77.
  21. Lukas Gianinazzi, Pavel Kalvoda, Alessandro De Palma, Maciej Besta, and Torsten Hoefler. Communication-avoiding parallel minimum cuts and connected components. In Proc. 23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pages 219-232. ACM, 2018. URL: https://doi.org/10.1145/3200691.3178504.
  22. Andrew V. Goldberg and Robert E. Tarjan. A new approach to the maximum-flow problem. Journal of the ACM, 35(4):921-940, 1988. URL: https://doi.org/10.1145/48014.61051.
  23. Ralph E. Gomory and Tien Chung Hu. Multi-terminal network flows. Journal of the Society for Industrial and Applied Mathematics, 9(4):551-570, 1961. URL: https://doi.org/10.1137/0109047.
  24. Lars Hagen and Andrew B Kahng. New spectral methods for ratio cut partitioning and clustering. IEEE Trans. on Computer-aided Design of Integrated Circuits and Systems, 11(9):1074-1085, 1992. URL: https://doi.org/10.1109/43.159993.
  25. Erez Hartuv and Ron Shamir. A clustering algorithm based on graph connectivity. Information Processing Letters, 76(4-6):175-181, 2000. URL: https://doi.org/10.1016/S0020-0190(00)00142-3.
  26. Monika Henzinger, Alexander Noe, and Christian Schulz. Shared-memory exact minimum cuts. In Proc. 2019 IEEE International Parallel and Distributed Processing Symposium (IPDPS 2019), pages 13-22. IEEE, 2019. URL: https://doi.org/10.1109/IPDPS.2019.00013.
  27. Monika Henzinger, Alexander Noe, and Christian Schulz. Shared-memory branch-and-reduce for multiterminal cuts. In Proc. 22nd Symposium on Algorithm Engineering and Experiments (ALENEX 2020), pages 42-55. SIAM, 2020. URL: https://doi.org/10.1137/1.9781611976007.4.
  28. Monika Henzinger, Alexander Noe, Christian Schulz, and Darren Strash. Practical minimum cut algorithms. ACM Journal of Experimental Algorithmics, 23, 2018. URL: https://doi.org/10.1145/3274662.
  29. Demian Hespe, Sebastian Lamm, Christian Schulz, and Darren Strash. We got you covered: The winning solver from the PACE 2019 challenge, vertex cover track. In Proc. SIAM Workshop on Combinatorial Scientific Computing 2020 (CSC20), pages 1-11. SIAM, 2020. URL: https://doi.org/10.1137/1.9781611976229.1.
  30. Demian Hespe, Christian Schulz, and Darren Strash. Scalable kernelization for maximum independent sets. In Proc. 20th Workshop on Algorithm Engineering and Experiments (ALENEX 2018), pages 223-237, 2018. URL: https://doi.org/10.1137/1.9781611975055.19.
  31. Michael Jünger, Giovanni Rinaldi, and Stefan Thienel. Practical performance of efficient minimum cut algorithms. Algorithmica, 26(1):172-195, 2000. URL: https://doi.org/10.1007/s004539910009.
  32. Goossen Kant. Algorithms for drawing planar graphs. PhD thesis, Utrecht University, 1993. URL: https://www.persistent-identifier.nl/urn:nbn:nl:ui:10-1874-842.
  33. David R Karger. Minimum cuts in near-linear time. Journal of the ACM, 47(1):46-76, 2000. URL: https://doi.org/10.1145/331605.331608.
  34. David R. Karger. A randomized fully polynomial time approximation scheme for the all-terminal network reliability problem. SIAM Review, 43(3):499-522, 2001. URL: https://doi.org/10.1137/S0036144501387141.
  35. David R Karger and Clifford Stein. A new approach to the minimum cut problem. Journal of the ACM, 43(4):601-640, 1996. URL: https://doi.org/10.1145/234533.234534.
  36. Alexander V Karzanov and Eugeniy A Timofeev. Efficient algorithm for finding all minimal edge cuts of a nonoriented graph. Cybernetics and Systems Analysis, 22(2):156-162, 1986. URL: https://doi.org/10.1007/BF01074775.
  37. Krzysztof Kiljan and Marcin Pilipczuk. Experimental evaluation of parameterized algorithms for feedback vertex set. In Proc. 17th International Symposium on Experimental Algorithms (SEA 2018), volume 103 of LIPIcs, pages 12:1-12:12, 2018. URL: https://doi.org/10.4230/LIPIcs.SEA.2018.12.
  38. Viatcheslav Korenwein, André Nichterlein, Rolf Niedermeier, and Philipp Zschoche. Data reduction for maximum matching on real-world graphs: Theory and experiments. In Proc. 26th European Symposium on Algorithms (ESA 2018), volume 112 of LIPIcs, pages 53:1-53:13, 2018. URL: https://doi.org/10.4230/LIPIcs.ESA.2018.53.
  39. Arie MCA Koster, Hans L Bodlaender, and Stan PM Van Hoesel. Treewidth: computational experiments. Electronic Notes in Discrete Mathematics, 8:54-57, 2001. URL: https://doi.org/10.1016/S1571-0653(05)80078-2.
  40. Balakrishnan Krishnamurthy. An improved min-cut algorithm for partitioning VLSI networks. IEEE Trans. on Computers, 33(5):438-446, 1984. URL: https://doi.org/10.1109/TC.1984.1676460.
  41. Sebastian Lamm, Christian Schulz, Darren Strash, Robert Williger, and Huashuo Zhang. Exactly solving the maximum weight independent set problem on large real-world graphs. In Proc. 21st Workshop on Algorithm Engineering and Experiments (ALENEX 2019), pages 144-158. SIAM, 2019. URL: https://doi.org/10.1137/1.9781611975499.12.
  42. Tobias Maier, Peter Sanders, and Roman Dementiev. Concurrent hash tables: Fast and general(?)! ACM Trans. Parallel Comput., 5(4), 2019. URL: https://doi.org/10.1145/3309206.
  43. Hiroshi Nagamochi and Toshihide Ibaraki. Computing edge-connectivity in multigraphs and capacitated graphs. SIAM Journal on Discrete Mathematics, 5(1):54-66, 1992. URL: https://doi.org/10.1137/0405004.
  44. Hiroshi Nagamochi and Tiko Kameda. Canonical cactus representation for minimum cuts. Japan Journal of Industrial and Applied Mathematics, 11(3):343-361, 1994. URL: https://doi.org/10.1007/BF03167227.
  45. Hiroshi Nagamochi, Yoshitaka Nakao, and Toshihide Ibaraki. A fast algorithm for cactus representations of minimum cuts. Japan Journal of Industrial and Applied Mathematics, 17(2):245-264, 2000. URL: https://doi.org/10.1007/BF03167346.
  46. Hiroshi Nagamochi, Tadashi Ono, and Toshihide Ibaraki. Implementing an efficient minimum capacity cut algorithm. Math. Prog., 67(1):325-341, 1994. URL: https://doi.org/10.1007/BF01582226.
  47. Dalit Naor, Dan Gusfield, and Charles Martel. A fast algorithm for optimally increasing the edge connectivity. SIAM Journal on Computing, 26(4):1139-1165, 1997. URL: https://doi.org/10.1137/S0097539792234226.
  48. Dalit Naor and Vijay V Vazirani. Representing and enumerating edge connectivity cuts in RNC. In Proc. 2nd Workshop on Algorithms and Data Structures (WADS 1991), volume 519 of LNCS, pages 273-285. Springer, 1991. URL: https://doi.org/10.1007/BFb0028269.
  49. Manfred Padberg and Giovanni Rinaldi. A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems. SIAM Review, 33(1):60-100, 1991. URL: https://doi.org/10.1137/1033004.
  50. Jean-Claude Picard and Maurice Queyranne. On the structure of all minimum cuts in a network and applications. In Combinatorial Optimization II, pages 8-16. Springer, 1980. URL: https://doi.org/10.1007/BFb0120902.
  51. Aparna Ramanathan and Charles J Colbourn. Counting almost minimum cutsets with reliability applications. Mathematical Programming, 39(3):253-261, 1987. URL: https://doi.org/10.1007/BF02592076.
  52. Thomas Schank and Dorothea Wagner. Finding, counting and listing all triangles in large graphs, an experimental study. In Proc. 4th International Workshop on Experimental and Efficient Algorithms (WEA 2005), volume 3503 of LNCS, pages 606-609. Springer, 2005. URL: https://doi.org/10.1007/11427186_5.
  53. Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8):888-905, 2000. URL: https://doi.org/10.1109/34.868688.
  54. Hisao Tamaki. Positive-instance driven dynamic programming for treewidth. In Proc. 25th European Symposium on Algorithms (ESA 2017), volume 87 of LIPIcs, pages 68:1-68:13, 2017. URL: https://doi.org/10.4230/LIPIcs.ESA.2017.68.
  55. Robert Tarjan. Depth-first search and linear graph algorithms. SIAM Journal on Computing, 1(2):146-160, 1972. URL: https://doi.org/10.1137/0201010.
  56. Reginald P Tewarson. Sparse matrices. Academic Press, 1973. Google Scholar
  57. Zhenyu Wu and Richard Leahy. An optimal graph theoretic approach to data clustering: Theory and its application to image segmentation. IEEE Trans. on Pattern Analysis and Machine Intelligence, pages 1101-1113, 1993. URL: https://doi.org/10.1109/34.244673.
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