Practical Minimum Cut Algorithms

Abstract

The minimum cut problem for an undirected edge-weighted graph asks us to divide its set of nodes into two blocks while minimizing the weight sum of the cut edges. Here, we introduce a linear-time algorithm to compute near-minimum cuts. Our algorithm is based on cluster contraction using label propagation and Padberg and Rinaldi’s contraction heuristics [SIAM Review, 1991]. We give both sequential and shared-memory parallel implementations of our algorithm. Extensive experiments on both real-world and generated instances show that our algorithm finds the optimal cut on nearly all instances significantly faster than other state-of-the-art exact algorithms, and our error rate is lower than that of other heuristic algorithms. In addition, our parallel algorithm runs a factor 7.5× faster on average when using 32 threads. To further speed up computations, we also give a version of our algorithm that performs random edge contractions as preprocessing. This version achieves a lower running time and better parallel scalability at the expense of a higher error rate.

References

1. Yaroslav Akhremtsev, Peter Sanders, and Christian Schulz. 2014. (Semi-) external algorithms for graph partitioning and clustering. In 2015 Proceedings of the 17th Workshop on Algorithm Engineering and Experiments (ALENEX’14). SIAM, 33--43.
2. Yaroslav Akhremtsev, Peter Sanders, and Christian Schulz. 2017. High-quality shared-memory graph partitioning. arXiv preprint arXiv:1710.08231.
3. Richard J. Anderson and Heather Woll. 1991. Wait-free parallel algorithms for the union-find problem. In Proceedings of the 23rd Annual ACM Symposium on Theory of Computing (STOC’91). ACM, 370--380.
4. D. Bader, A. Kappes, H. Meyerhenke, P. Sanders, C. Schulz, and D. Wagner. 2014. Benchmarking for graph clustering and partitioning. In Encyclopedia of Social Network Analysis and Mining, Reda Alhajj and Jon Rokne (Eds.). Springer, 1--11.
5. Vladimir Batagelj and Matjaz Zaversnik. 2003. An O(m) algorithm for cores decomposition of networks. arXiv preprint cs/0310049.
6. Paolo Boldi, Marco Rosa, Massimo Santini, and Sebastiano Vigna. 2011. Layered label propagation: A multiresolution coordinate-free ordering for compressing social networks. In Proceedings of the 20th International Conference on World Wide Web, Sadagopan Srinivasan, Krithi Ramamritham, Arun Kumar, M. P. Ravindra, Elisa Bertino, and Ravi Kumar (Eds.). ACM, 587--596.
7. Paolo Boldi and Sebastiano Vigna. 2004. The webgraph framework I: Compression techniques. In Proceedings of the 13th International World Wide Web Conference (WWW’04). ACM, New York, 595--601.
8. Deepayan Chakrabarti and Christos Faloutsos. 2006. Graph mining: Laws, generators, and algorithms. Comput. Surveys 38, 1 (2006), 2.
9. Chandra S. Chekuri, Andrew V. Goldberg, David R. Karger, Matthew S. Levine, and Cliff Stein. 1997. Experimental study of minimum cut algorithms. In Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’97). SIAM, 324--333.
10. Leonardo Dagum and Ramesh Menon. 1998. OpenMP: An industry standard API for shared-memory programming. IEEE Comput. Sci. Eng. 5, 1 (1998), 46--55.
11. Lester R. Ford and Delbert R. Fulkerson. 1956. Maximal flow through a network. Can. J. Math. 8, 3 (1956), 399--404.
12. Bernard A. Galler and Michael J. Fisher. 1964. An improved equivalence algorithm. Commun. ACM 7, 5 (1964), 301--303.
13. Lukas Gianinazzi, Pavel Kalvoda, Alessandro De Palma, Maciej Besta, and Torsten Hoefler. 2018. Communication-avoiding parallel minimum cuts and connected components. In Proceedings of the 23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. ACM, 219--232.
14. Andrew V. Goldberg and Robert E. Tarjan. 1988. A new approach to the maximum-flow problem. J. ACM 35, 4 (1988), 921--940.
15. Ralph E. Gomory and Tien Chung Hu. 1961. Multi-terminal network flows. J. Soc. Indust. Appl. Math. 9, 4 (1961), 551--570.
16. Jianxiu Hao and James B. Orlin. 1992. A faster algorithm for finding the minimum cut in a graph. In Proceedings of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 165--174.
17. Monika Henzinger, Satish Rao, and Di Wang. 2017. Local flow partitioning for faster edge connectivity. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 1919--1938.
18. Pili Hu and Wing Cheong Lau. 2013. A survey and taxonomy of graph sampling. arXiv preprint arXiv:1308.5865.
19. Michael Jünger, Giovanni Rinaldi, and Stefan Thienel. 2000. Practical performance of efficient minimum cut algorithms. Algorithmica 26, 1 (2000), 172--195.
20. David R. Karger. 2000. Minimum cuts in near-linear time. J. ACM 47, 1 (2000), 46--76.
21. David R. Karger. 2001. A randomized fully polynomial time approximation scheme for the all-terminal network reliability problem. SIAM Rev. 43, 3 (2001), 499--522.
22. David R. Karger and Clifford Stein. 1996. A new approach to the minimum cut problem. J. ACM 43, 4 (1996), 601--640.
23. George Karypis and Vipin Kumar. 1998. Metis: A software package for partitioning unstructured graphs, partitioning meshes, and computing fill-reducing orderings of sparse matrices, Version 4.
24. Ken-ichi Kawarabayashi and Mikkel Thorup. 2015. Deterministic global minimum cut of a simple graph in near-linear time. In Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC’15). ACM, 665--674.
25. Farzad Khorasani, Rajiv Gupta, and Laxmi N. Bhuyan. 2015. Scalable SIMD-efficient graph processing on GPUs. In Proceedings of the 24th International Conference on Parallel Architectures and Compilation Techniques (PACT’15). 39--50.
26. Kishore Kothapalli, Sriram V. Pemmaraju, and Vivek Sardeshmukh. 2013. On the analysis of a label propagation algorithm for community detection. In Proceedings of the 14th International Conference on Distributed Computing and Networking (ICDCN’3), Lecture Notes in Computer Science, Vol. 7730. Springer, 255--269.
27. Dmitri Krioukov, Fragkiskos Papadopoulos, Maksim Kitsak, Amin Vahdat, and Marián Boguná. 2010. Hyperbolic geometry of complex networks. Phys. Rev. E 82, 3 (2010), 036106.
28. Balakrishnan Krishnamurthy. 1984. An improved min-cut algorithm for partitioning VLSI networks. IEEE Trans. Comput. 33, 5 (1984), 438--446.
29. Tobias Maier, Peter Sanders, and Roman Dementiev. 2016. Concurrent hash tables: Fast and general?(!). In Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP’16). ACM, 34:1--34:2.
30. David W. Matula. 1993. A linear time 2+ϵ approximation algorithm for edge connectivity. In Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 500--504.
31. Hiroshi Nagamochi and Toshihide Ibaraki. 1992. Computing edge-connectivity in multigraphs and capacitated graphs. SIAM J. Discr. Math. 5, 1 (1992), 54--66.
32. Hiroshi Nagamochi, Tadashi Ono, and Toshihide Ibaraki. 1994. Implementing an efficient minimum capacity cut algorithm. Math. Program. 67, 1 (1994), 325--341.
33. Manfred Padberg and Giovanni Rinaldi. 1990. An efficient algorithm for the minimum capacity cut problem. Math. Program. 47, 1 (1990), 19--36.
34. Manfred Padberg and Giovanni Rinaldi. 1991. A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems. SIAM Rev. 33, 1 (1991), 60--100.
35. Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. 1999. The PageRank Citation Ranking: Bringing Order to the Web. Technical Report. Stanford InfoLab.
36. Usha Nandini Raghavan, Réka Albert, and Soundar Kumara. 2007. Near linear time algorithm to detect community structures in large-scale networks. Phys. Rev. E 76, 3 (2007), 036106.
37. Aparna Ramanathan and Charles J. Colbourn. 1987. Counting almost minimum cutsets with reliability applications. Math. Program. 39, 3 (1987), 253--261.
38. Thomas Schank and Dorothea Wagner. 2005. Finding, counting and listing all triangles in large graphs, an experimental study. In Proceedings of the 4th International Workshop on Experimental and Efficient Algorithms (WEA’05), Lecture Notes in Computer Science, Vol. 3503. Springer, 606--609.
39. Stephen B. Seidman. 1983. Network structure and minimum degree. Soc. Netw. 5, 3 (1983), 269--287.
40. Christian L. Staudt and Henning Meyerhenke. 2013. Engineering high-performance community detection heuristics for massive graphs. In Proceedings of the 42nd International Conference on Parallel Processing (ICPP’13). IEEE, 180--189.
41. Christian L. Staudt, Aleksejs Sazonovs, and Henning Meyerhenke. 2014. NetworKit: An interactive tool suite for high-performance network analysis. CoRR, abs/1403.3005.
42. Clifford Stein and Matthew Levine. Minimum cut code. Retrieved June 9, 2017 from http://www.columbia.edu/∼cs2035/code.html.
43. Mechthild Stoer and Frank Wagner. 1997. A simple min-cut algorithm. J. ACM 44, 4 (1997), 585--591.
44. Moritz von Looz, Henning Meyerhenke, and Roman Prutkin. 2015. Generating random hyperbolic graphs in subquadratic time. In Proceedings of the 26th International Symposium on Algorithms and Computation (ISAAC’15), Lecture Notes in Computer Science, Vol. 9472. Springer, 467--478.
45. Norbert Zeh. 2002. I/O-efficient graph algorithms. EEF Summer School on Massive Data Sets. Retrieved June 11, 2018 from https://www.cs.au.dk/∼gerth/MassiveData02/notes/zeh.pdf. (2002).

Index Terms

• Mathematics of computing

  • Discrete mathematics

    • Graph theory

      • Graph algorithms

  • Probability and statistics

    • Probabilistic algorithms

• Theory of computation

  • Design and analysis of algorithms

    • Graph algorithms analysis

      • Sparsification and spanners