# Fast and Compact Graph Cuts for the Boykov-Kolmogorov Algorithm

arXiv: https://arxiv.org/abs/2605.13402 · HTML: https://mlsanity.com/paper/2605.13402/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 61 references that are in the map.
- First posted on arXiv 13 May 2026.

## Builds on (most cited first, 11 of 11)

- [Graph-Cut RANSAC](https://mlsanity.com/paper/1706.00984/) (2017)
- [Event-based Motion Segmentation with Spatio-Temporal Graph Cuts](https://mlsanity.com/paper/2012.08730/) (2020)
- [Multimodal Style Transfer via Graph Cuts](https://mlsanity.com/paper/1904.04443/) (2019)
- [GaussianCut: Interactive segmentation via graph cut for 3D Gaussian Splatting](https://mlsanity.com/paper/2411.07555/) (2024)
- [Fusion Moves for Graph Matching](https://mlsanity.com/paper/2101.12085/) (2021)
- [Deep LOGISMOS: Deep Learning Graph-based 3D Segmentation of Pancreatic Tumors on CT scans](https://mlsanity.com/paper/1801.08599/) (2018)
- [Fast Graph-Cut Based Optimization for Practical Dense Deformable Registration of Volume Images](https://mlsanity.com/paper/1810.08427/) (2018)
- [gcDLSeg: Integrating Graph-cut into Deep Learning for Binary Semantic Segmentation](https://mlsanity.com/paper/2312.04713/) (2023)
- [Efficient optimization for Hierarchically-structured Interacting Segments (HINTS)](https://mlsanity.com/paper/1703.10530/) (2017)
- [Review of Serial and Parallel Min-Cut/Max-Flow Algorithms for Computer Vision](https://mlsanity.com/paper/2202.00418/) (2022)
- [Conditional gradients for total variation regularization with PDE constraints: a graph cuts approach](https://mlsanity.com/paper/2310.19777/) (2023)

## Abstract (arXiv)

Computing a minimum s-t cut in a graph is a solution to a wide range of computer vision problems, and is often done using the Boykov-Kolmogorov (BK) algorithm. In this paper, we revisit the BK algorithm from both a theoretical and practical point of view. We improve the analysis of the time complexity of the BK algorithm to O(mn|C|) and propose a new algorithm, the fast and compact BK (fcBK) algorithm, with a time complexity of O(m|C|), where m, n, and |C| are the number of edges, number of vertices, and the capacity of the cut, respectively. We additionally propose a compact graph representation that allows our implementation to find a minimum s-t cut in a graph with upwards of 109 vertices and 1010 edges on a machine with 128 GB of memory. We find our implementation of the BK algorithm to be the fastest available implementation of the BK algorithm when evaluating on a comprehensive set of benchmark datasets, highlighting the importance of memory-efficient implementations. We make our implementations publicly available for further research and implementation development within minimum s-t cut algorithms.