Overview
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. It is a fundamental graph problem with many applications in different fields, such as network reliability, where assuming equal failure probability edges, the smallest edge cut in the network has the highest chance to disconnect the network; in VLSI design, where the minimum cut can be used to minimize the number of connections between microprocessor blocks; and as a subproblem in branch-and-cut algorithms for the Traveling Salesman Problem (TSP) and other combinatorial problems.VieCut - Vienna Minimum Cuts -- is a shared-memory parallel heuristic algorithm for the minimum cut problem. Based on the algorithm we also present a fast and exact shared-memory parallel algorithm for the minimum cut problem. We provide it here as easy to use open source software. The algorithm is based on the label propagation algorithm, the contraction tests of Padberg and Rinaldi and the minimum cut algorithm of Nagamochi et al. and computes minimum cuts of huge networks fast and with use of shared-memory parallelism. While VieCut can not guarantee solution quality, in practice the algorithm outputs better cuts than other inexact algorithms in significantly lower time, especially when using shared-memory parallelism. This codebase also includes a fast and exact shared-memory parallel based on VieCut and the algorithm of Nagamochi et al. Using the high-quality cuts given by VieCut the algorithm can detect and contract contractible edges fast and in parallel. Using these techniques we can compute exact minimum cuts significantly faster than the state of the art, sometimes with speedups of more than an order of magnitude.
Additionally we give a branch-and-reduce algorithm for the multiterminal cut problem. The multiterminal cut problem is the NP-hard generalization of the minimum s-t-cut problem to more than two terminal vertices. Our algorithm combines a multitude of kernelization routines with a sophisticated branching routine and is able to solve this problem on some very large instances. Even if the algorithm is not able to guarantee optimality of its solution in a problem, it gives a high-quality approximation.
News:
13th December 2019: Published instances used for paper Shared-Memory Branch-and-Reduce for Multiterminal Cuts. Please see Downloads below.
12th August 2019: Published ArXiv Report (Shared-Memory Branch-and-Reduce for Multiterminal Cuts). Link to PDF.
21st May 2019: We presented our paper "Shared-memory Exact Minimum Cuts" at IPDPS 2019
7th January 2019: Released VieCut v1.00.
16th August 2018: Published ArXiv Report (Shared-memory Exact Minimum Cuts). Link to PDF.
7th January 2018 We presented our paper "Practical Minimum Cut Algorithms" at ALENEX 2018
27th August 2017: Published ArXiv Report (Practical Minimum Cut Algorithms). Link to PDF.
License
The program is licenced under the MIT license.If you publish results using our algorithms, please acknowledge our work by referencing all applicable papers:
@article{Henzinger2018Practical,
AUTHOR = {Henzinger, Monika and Noe, Alexander and Schulz, Christian and Strash, Darren},
TITLE = {{Practical Minimum Cut Algorithms}},
JOURNAL={Journal of Experimental Algorithmics (JEA)},
VOLUME={23},
NUMBER={1},
PAGES={1--8},
YEAR = {2018},
PUBLISHER={ACM},
}
@inproceedings{henzinger2019shared,
AUTHOR = {Henzinger, Monika and Noe, Alexander and Schulz, Christian},
TITLE = {{Shared-memory Exact Minimum Cuts}},
BOOKTITLE = {2019 IEEE International Parallel and Distributed Processing Symposium (IPDPS)},
PAGES = {13--22},
ORGANIZATION = {IEEE},
YEAR = {2019}
}
@inproceedings{henzinger2019branch,
AUTHOR = {Henzinger, Monika and Noe, Alexander and Schulz, Christian},
TITLE = {{Shared-memory Branch-and-Reduce for Multiterminal Cuts}},
JOURNAL = {arXiv preprint arXiv:1908.04141},
YEAR = {2019}
}
The algorithms that are included for download are mainly based on the following publications:
- Monika Henzinger, Alexander Noe, Christian Schulz and Darren Strash. Practical Minimum Cut Algorithms. Proceedings of the Twentieth Workshop on Algorithm Engineering and Experiments (ALENEX'18). 2018. Download PDF.
- Monika Henzinger, Alexander Noe and Christian Schulz. Shared-memory Exact Minimum Cuts. 2019. 2019 IEEE International Parallel and Distributed Processing Symposium (IPDPS) Download PDF.
- Monika Henzinger, Alexander Noe and Christian Schulz. Shared-memory Branch-and-Reduce for Multiterminal Cuts. 2019. (to appear at ALENEX'20) Download PDF.
Download
- Code and user guide available on GitHub here
- viecutv1_00.tar.gz (submodules accessed on 7. January 2019)
- Instances used for multiterminal cut problem: instances.tar.gz
Support
- Write us an email if you need support!
- We are glad for any comments and error reports (or even bug fixes or feature requests) that you send us.