VieCut 1.00

VieCut is a library of shared-memory parallel algorithms for the minimum cut problem on undirected edge-weighted graphs. Part of the KaHIP organization.

Quick Start

Install via Homebrew (Linux only)

brew install KaHIP/kahip/viecut

Or build from source

git clone --recursive https://github.com/KaHIP/VieCut.git && cd VieCut
mkdir build && cd build && cmake .. -DCMAKE_BUILD_TYPE=Release -DUSE_TCMALLOC=OFF && make

Run

# 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 4

When installed via Homebrew, use viecut_mincut, viecut_mincut_parallel, etc. directly.

Executables

| 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 |

Command Line Usage

./build/mincut [options] <graph-file> <algorithm>
./build/mincut_parallel [options] <graph-file> <algorithm>

Algorithms

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 |

Options

| 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 |

Examples

# 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 cactus

Multiterminal Cut

The 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 |

Graph Format

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]
...

Building from Source

Requirements

C++17 compiler (GCC 7+ or Clang 11+)
CMake 3.9+
OpenMP
MPI (for multiterminal cut)
TCMalloc (optional, for performance)

Build

git clone --recursive https://github.com/KaHIP/VieCut.git && cd VieCut
mkdir build && cd build
cmake .. -DCMAKE_BUILD_TYPE=Release
make

To build without TCMalloc:

cmake .. -DCMAKE_BUILD_TYPE=Release -DUSE_TCMALLOC=OFF

Sequential and parallel executables are placed in build/.

Related Projects

| Project | Description | |:--------|:------------| | KaHIP | Karlsruhe High Quality Graph Partitioning | | fpt-max-cut | FPT-based maximum cut solvers |

Licence

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}
}

VieCut

Install / Use

README