VieCut is a library of shared-memory parallel algorithms for the minimum cut problem on undirected edge-weighted graphs. Part of the KaHIP organization.
Python Interface: An easy-to-use Python interface for this software is available in CHSZLabLib.
| What it solves | Find the minimum edge cut that separates a graph into two (or more) components |
| Algorithms | Inexact heuristic (VieCut), exact parallel (NOI-based), cactus representation, multiterminal cut |
| Parallelism | Shared-memory via OpenMP; sequential versions included |
| Interfaces | CLI |
| Requires | C++17 compiler, CMake 3.9+, OpenMP, MPI (multiterminal cut only) |
brew install KaHIP/kahip/viecutgit clone --recursive https://github.com/KaHIP/VieCut.git && cd VieCut
mkdir build && cd build && cmake .. -DCMAKE_BUILD_TYPE=Release -DUSE_TCMALLOC=OFF && make# Heuristic minimum cut (fast, near-optimal)
./build/mincut network.graph vc
# Exact minimum cut (parallel)
./build/mincut_parallel network.graph exact
# Find all minimum cuts (cactus representation)
./build/mincut_parallel network.graph cactus
# Multiterminal cut (NP-hard, branch-and-reduce)
./build/multiterminal_cut network.graph -k 4When installed via Homebrew, use viecut_mincut, viecut_mincut_parallel, etc. directly.
| Binary | Parallel | Description |
|---|---|---|
mincut |
mincut_parallel |
Minimum cut with choice of algorithm |
multiterminal_cut |
Branch-and-reduce multiterminal cut (MPI) | |
kcore |
kcore_parallel |
k-core decomposition |
mincut_contract |
mincut_contract_parallel |
Minimum cut with random edge contraction |
mincut_recursive |
mincut_recursive_parallel |
Recursive minimum cut on largest SCC |
./build/mincut [options] <graph-file> <algorithm>
./build/mincut_parallel [options] <graph-file> <algorithm>
Sequential:
| Algorithm | Flag | Description |
|---|---|---|
| VieCut | vc |
Fast heuristic, near-optimal in practice |
| Nagamochi-Ono-Ibaraki | noi |
Classic exact algorithm |
| Karger-Stein | ks |
Randomized contraction |
| Matula | matula |
(2+e)-approximation |
| Padberg-Rinaldi | pr |
Contraction rules |
| Cactus | cactus |
Find all minimum cuts |
Parallel:
| Algorithm | Flag | Description |
|---|---|---|
| Inexact | inexact |
Parallel VieCut heuristic |
| Exact | exact |
Parallel exact minimum cut |
| Cactus | cactus |
Parallel cactus of all minimum cuts |
| Option | Description | Default |
|---|---|---|
-p <int> |
Number of processors (parallel only) | all |
-i <int> |
Number of iterations | 1 |
-q <type> |
Priority queue: bqueue, bstack, heap |
bqueue |
-s |
Compute and save the cut | off |
-o <file> |
Output file for the cut (requires -s) |
|
-b |
Find most balanced minimum cut (cactus only, requires -s) |
off |
-l |
Disable priority queue limiting | off |
# Parallel exact minimum cut with 8 threads, 5 iterations
./build/mincut_parallel -p 8 -i 5 network.graph exact
# Save cut to file
./build/mincut -s -o cut.txt network.graph noi
# Most balanced minimum cut
./build/mincut_parallel -s -b network.graph cactusThe multiterminal cut separates a set of terminal vertices from each other with minimum total cut weight. For |T|=2 this equals the minimum s-t-cut; for |T|>2 it is NP-hard. VieCut uses a shared-memory parallel branch-and-reduce approach.
./build/multiterminal_cut <graph-file> [options]
| Option | Description |
|---|---|
-f <file> |
Partition file assigning terminals |
-t <int> |
Add vertex as terminal (repeatable) |
-k <int> |
Use k highest-degree vertices as terminals |
-r <int> |
Use r random vertices as terminals |
-b <int> |
BFS expansion around terminals |
-p <int> |
Number of threads |
VieCut uses the METIS graph format. Graphs can be unweighted or edge-weighted (format flag 1).
<num_nodes> <num_edges> [format]
<neighbors of node 1> [weights]
<neighbors of node 2> [weights]
...
- C++17 compiler (GCC 7+ or Clang 11+)
- CMake 3.9+
- OpenMP
- MPI (for multiterminal cut)
- TCMalloc (optional, for performance)
git clone --recursive https://github.com/KaHIP/VieCut.git && cd VieCut
mkdir build && cd build
cmake .. -DCMAKE_BUILD_TYPE=Release
makeTo build without TCMalloc:
cmake .. -DCMAKE_BUILD_TYPE=Release -DUSE_TCMALLOC=OFFSequential and parallel executables are placed in build/.
| Project | Description |
|---|---|
| KaHIP | Karlsruhe High Quality Graph Partitioning |
| fpt-max-cut | FPT-based maximum cut solvers |
VieCut is free software provided under the MIT License. If you publish results using our algorithms, please cite the applicable papers:
@article{DBLP:journals/jea/HenzingerNSS18,
author = {Monika Henzinger and Alexander Noe and Christian Schulz and Darren Strash},
title = {Practical Minimum Cut Algorithms},
journal = {{ACM} J. Exp. Algorithmics},
volume = {23},
year = {2018},
doi = {10.1145/3274662}
}
@inproceedings{DBLP:conf/ipps/HenzingerN019,
author = {Monika Henzinger and Alexander Noe and Christian Schulz},
title = {Shared-Memory Exact Minimum Cuts},
booktitle = {2019 {IEEE} International Parallel and Distributed Processing Symposium ({IPDPS})},
pages = {13--22},
publisher = {{IEEE}},
year = {2019},
doi = {10.1109/IPDPS.2019.00013}
}
@inproceedings{DBLP:conf/esa/HenzingerN0S20,
author = {Monika Henzinger and Alexander Noe and Christian Schulz and Darren Strash},
title = {Finding All Global Minimum Cuts in Practice},
booktitle = {28th Annual European Symposium on Algorithms ({ESA} 2020)},
series = {LIPIcs},
volume = {173},
pages = {59:1--59:20},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2020},
doi = {10.4230/LIPIcs.ESA.2020.59}
}
@inproceedings{DBLP:conf/alenex/HenzingerN022,
author = {Monika Henzinger and Alexander Noe and Christian Schulz},
title = {Practical Fully Dynamic Minimum Cut Algorithms},
booktitle = {Proceedings of the 24th Symposium on Algorithm Engineering and Experiments ({ALENEX} 2022)},
pages = {13--26},
publisher = {{SIAM}},
year = {2022},
doi = {10.1137/1.9781611977042.2}
}
@inproceedings{DBLP:conf/alenex/HenzingerN020,
author = {Monika Henzinger and Alexander Noe and Christian Schulz},
title = {Shared-Memory Branch-and-Reduce for Multiterminal Cuts},
booktitle = {Proceedings of the 22nd Symposium on Algorithm Engineering and Experiments ({ALENEX} 2020)},
pages = {42--55},
publisher = {{SIAM}},
year = {2020},
doi = {10.1137/1.9781611976007.4}
}
@inproceedings{DBLP:conf/acda/HenzingerN021,
author = {Monika Henzinger and Alexander Noe and Christian Schulz},
title = {Faster Parallel Multiterminal Cuts},
booktitle = {Proceedings of the 2021 {SIAM} Conference on Applied and Computational Discrete Algorithms ({ACDA} 2021)},
pages = {100--110},
publisher = {{SIAM}},
year = {2021},
doi = {10.1137/1.9781611976830.10}
}