Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2605.13402 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910216158707712 |
|---|---|
| author | Mikkelstrup, Christian Møller Dahl, Anders Bjorholm Bille, Philip Dahl, Vedrana Andersen Gørtz, Inge Li |
| author_facet | Mikkelstrup, Christian Møller Dahl, Anders Bjorholm Bille, Philip Dahl, Vedrana Andersen Gørtz, Inge Li |
| contents | 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 $10^9$ vertices and $10^{10}$ 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_13402 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Fast and Compact Graph Cuts for the Boykov-Kolmogorov Algorithm Mikkelstrup, Christian Møller Dahl, Anders Bjorholm Bille, Philip Dahl, Vedrana Andersen Gørtz, Inge Li Computer Vision and Pattern Recognition Data Structures and Algorithms 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 $10^9$ vertices and $10^{10}$ 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. |
| title | Fast and Compact Graph Cuts for the Boykov-Kolmogorov Algorithm |
| topic | Computer Vision and Pattern Recognition Data Structures and Algorithms |
| url | https://arxiv.org/abs/2605.13402 |