If you have any questions, find any errors or would like to use this library but are unsure how, feel free to send me a message. I would be very happy to help you out!
This is the code repository to accompany our papers:
-
Henzinger, M., Noe, A., Schulz, C. and Strash, D., 2018. Practical Minimum Cut Algorithms. arXiv preprint arXiv:1708.06127.
-
Henzinger, M., Noe, A. and Schulz, C., 2019. Shared-memory Exact Minimum Cuts. arXiv preprint arXiv:1808.05458.
-
Henzinger, M., Noe, A., Schulz, C. and Strash, D., 2020. Finding All Global Minimum Cuts in Practice. arXiv preprint arxiv:2002.06948
-
Henzinger, M., Noe, A. and Schulz C., 2021. Practical Fully Dynamic Minimum Cut Algorithms arxiv:2101.05033
-
Henzinger, M., Noe, A. and Schulz, C., 2019. Shared-Memory Branch-and-Reduce for Multiterminal Cuts. arXiv preprint arXiv:1908.04141.
-
Henzinger, M., Noe, A. and Schulz, C., 2020. Faster Parallel Multiterminal Cuts. arXiv preprint arxiv:2004.11666
The instances used for the third paper can be found on the website for VieCut.
The papers can be freely accessed online in the arXiv.
If you use this code in the context of an academic publication, we ask that you cite the applicable papers:
@article{henzinger2018practical,
author = {Monika Henzinger and
Alexander Noe and
Christian Schulz and
Darren Strash},
title = {Practical Minimum Cut Algorithms},
journal = {{ACM} Journal of Experimental Algorithmics},
volume = {23},
year = {2018}
}
@inproceedings{henzinger2019shared,
author = {Henzinger, Monika and Noe, Alexander and Schulz, Christian},
title = {{Shared-memory Exact Minimum Cuts}},
booktitle={Proceedings of the 33rd International Parallel and Distributed Processing Symposium (IPDPS)},
year = {2019}
}
@article{henzinger2020finding,
title={Finding All Global Minimum Cuts in Practice},
author={Henzinger, Monika and Noe, Alexander and Schulz, Christian and Strash, Darren},
booktitle = {28th Annual European Symposium on Algorithms, {ESA} 2020, September
7-9, 2020, Pisa, Italy (Virtual Conference)},
year={2020}
}
@manuscript{henzinger2021practical,
title = {Practical Fully Dynamic Minimum Cut Algorithms},
author = {Henzinger, Monika and Noe, Alexander and Schulz, Christian},
journal = {arXiv preprint arXiv:2101.05033},
year = {2021}
}
@inproceedings{henzinger2020sharedmemory,
title = {Shared-Memory Branch-and-Reduce for Multiterminal Cuts},
author = {Monika Henzinger and Alexander Noe and Christian Schulz},
year = {2019},
booktitle = {Proc. of the Twenty-First Workshop on Algorithm Engineering and Experiments, {ALENEX} 2020},
publisher = {{SIAM}},
year = {2020},
primaryclass = {cs.DS}
}
@manuscript{henzinger2020faster,
title = {Faster Parallel Multiterminal Cuts},
author = {Henzinger, Monika and Noe, Alexander and Schulz, Christian},
journal = {arXiv preprint arXiv:2004.11666},
year = {2020}
}
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.
In our work, we present fast shared-memory parallel algorithms for the minimum cut problem.
In the first paper, Practical Minimum Cut Algorithm, we present the fast shared-memory parallel heuristic algorithm VieCut.
While the algorithm can not guarantee solution quality, in practice it usually outputs cuts that are minimal or very close.
Based on this algorithm and the algorithm of Nagamochi et al., in our paper Shared-memory Exact Minimum Cuts we present a fast shared-memory exact algorithm for the minimum cut problem. These algorithms significantly outperform the state of the art.
In order to compile the code you need a C++ compiler that supports c++-20, such as clang++-11, and cmake.
As we use TCMalloc to allocate and deallocate memory, you need to have google-perftools installed.
If you haven't installed these dependencies, please do so via your package manager
sudo apt install clang-11 cmake libgoogle-perftools-dev
To compile the code use the following commands
git submodule update --init --recursive
mkdir build
cd build
cmake ..
make
We also offer a compile script compile.sh which compiles the executables and runs tests.
All of our programs are compiled both for single threaded and shared-memory parallel use.
The name of the parallel executable is indicated by appending it with _parallel.
The executables can be found in subfolder build.
The main executable in our program is mincut. The shared-memory parallel executable using OpenMP is mincut_parallel
This executable can be used to compute the minimum cut of a given graph with different algorithms.
We use the METIS graph format for all graphs.
Run any minimum cut algorithm using the following command
./build/mincut [options] /path/to/graph.metis <algorithm>
./build/mincut_parallel [options] /path/to/graph.metis <algorithm>
For use one of the following:
vc-VieCut[HNSS'18]noi- Algorithm of Nagamochi et al. [NOI'94]ks- Algorithm of Karger and Stein [KS'96]matula- Approximation Algorithm of Matula [Matula'93]pr- Repeated application of Padberg-Rinaldi contraction rules [PR'91]cactus- Find all minimum cuts and give the cactus that represents them. [HNSS'20]
when parallelism is enabled, use one of the following:
inexact- shared-memory parallel version ofVieCut[HNSS'18]exact- exact shared-memory parallel minimum cut [HNS'19a]cactus- Find all minimum cuts and give the cactus that represents them. [HNSS'20]
-q- Priority queue implementation ('bqueue,bstack,heap, see [HNS'19a] for details)-i- Number of iterations (default: 1)-l- Disable limiting of values in priority queue (only relevant fornoiandexact, see [HNS'19a])-p- [Only formincut_parallel] Usepprocessors (multiple values possible)-s- Compute and save minimum cut. The cut will be written to disk in a file which contains one line per node, either0or1depending on which side of the cut the node is.-o- [-sneeds to be enabled as well] Path of output file. If this is set, we print the minimum cut to file.-b- [Only for algorithmcactus,-sneeds to be enabled as well] Find most balanced minimum cut and print its balance.
The following command
./build/mincut_parallel -q bqueue -i 3 -p 2 -p 12 /path/to/my/graph.metis exact
runs algorithm exact using the BQueue priority queue implementation for 3 iterations both with 2 and 12 processors.
For each of the runs we print running time and results, as well as a few informations about the graph and algorithm configuration.
The multiterminal cut of a graph G and a set of terminals T is to find the minimum cut of G that separates all terminals from each other. For |T|=2 this is equal to the minimum s-t-cut problem, for |T|>2, the problem is NP-hard. We solve the problem using a branch-and-reduce approach which finds a hard kernel by applying reduction rules and then branching on edges adjacent to a terminal. For a more detailed description, we refer the reader to [HNS'19b]. The algorithm is shared-memory parallel and uses OpenMP.
./build/multiterminal_cut /path/to/graph.metis \[options]
-f- Path to partition file. This file has one line for each vertex. A value of 0 to |T|-1 indicates which terminal a vertex belongs to, otherwise a value of |T| indicates that the vertex does not belong to a terminal.-t- Add vertextas a terminal.-k- Find multiterminal cut betweenkvertices with highest vertex degree.-r- Find multiterminal cut betweenrrandom vertices.-b- Run BFS around each terminal and add up tobvertices discovered first to each terminal.-p- Number of threads (default: OMP_NUM_THREADS, which defaults to the number of hardware threads).
The following command
./build/multiterminal_cut /path/to/my/graph.metis -f /path/to/my/partition_file -p 12 -c 1
finds the multiterminal cut as given by the graph and partition file using 12 threads and all except for the high-connectivity kernelization (see [HNS'19b] for further details) rules enabled.
As most real-world graphs contain vertices with degree 1 and multiple connected components, finding the minimum cut is
as easy as finding the minimum degree or checking whether the graph has multiple connected components.
In order to create harder instances for [HNS'19a] and [HNSS'18] we use the cores decomposition of the graph.
The k-core of a graph is the largest subgraph of the graph, in which every node has at least degree k in the k-core.
We use the executable kcore to find k-cores of a graph where the minimum cut is not equal to the minimum degree.
If the minimum cut is not equal to the minimum degree, the k-core graph is written both in METIS and in DIMACS format.
./build/kcore <options> /path/to/graph.metis
with following options:
-l- search for the lowest value of k where the minimum cut of the k-core is not equal to the minimum degree-c- disable testing for the minimum cut, just compute cores decomposition and write k-core graphs to disk-k- compute k-core for k
For example, to compute the 5- and 10-cores of a graph without minimum cut testing, use the following command
./build/kcore -c -k 5 -k 10 /path/to/graph.metis
The executable mincut_contract runs a version of mincut that begins with contracting random edges.
This idea is taken from the algorithm or Karger and Stein [KS96], which contracts random edges and recurses on the contracted graph.
Mincut contract begins by contracting random edges until a user-defined number of vertices is left.
Afterwards we run a minimum cut algorithm on the contracted graph.
Usage is similar to mincut and can be combined with any minimum cut algorithm.
./build/mincut_contract [options] /path/to/graph.metis <algorithm>
-q- Priority queue implementation ('bqueue,bstack,heap, see [HNS'19a] for details)-i- Number of iterations (default: 1)-l- Disable limiting of values in priority queue (only relevant fornoiandexact, see [HNS'19a])-p- Usepprocessors (multiple values possible)-c- Contraction factor: we contract until only n*(1-c) vertices are left.-s- Compute and save minimum cut.
The executable mincut_recusive runs an exact minimum cut algorithm (exact in parallel, noi otherwise)
on a graph and creates a graph for the largest SCC of the larger block of the cut.
We then run the minimum cut algorithm on this graph and repeat this process until the minimum cut is equal to the minimum degree.
This can be used to create subgraphs of a graph that have different minimum cuts.
./build/mincut_recursive [options] /path/to/graph.metis
-o- Write all graphs to disk (DIMACS and METIS format) where the minimum cut is larger than the minimum cut of the previous graph.
[BZ'03] - Batagelj, V. and Zaversnik, M., 2003. An O(m) algorithm for cores decomposition of networks.
[HNS'19a] - Henzinger, M., Noe, A. and Schulz, C., 2019. Shared-memory Exact Minimum Cuts.
[HNS'19b] - Henzinger, M., Noe, A. and Schulz, C., 2019. Shared-memory Branch-and-reduce for Multiterminal Cuts.
[HNSS'18] - Henzinger, M., Noe, A., Schulz, C. and Strash, D., 2018. Practical Minimum Cut Algorithms.
[KS'96] - Karger, D. and Stein, C., 1996. A new approach to the minimum cut problem.
[Matula'93] - Matula, D., 1993. A linear time (2 + ε)-approximation algorithm for edge connectivity
[NOI'94] - Nagamochi, H., Ono, T. and Ibaraki, T., 1994. Implementing an efficient minimum capacity cut algorithm.
[PR'91] - Padberg, M. and Rinaldi G., 1991. An efficient algorithm for the minimum capacity cut problem.
[SW'97] - Stoer, M. and Wagner, F., 1997. A simple min-cut algorithm.