# A Message Passing Algorithm for the Minimum Cost Multicut Problem

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Dec 2016.

## Built on by (most cited first, 11 of 11)

- [Correlation Clustering via Strong Triadic Closure Labeling: Fast Approximation Algorithms and Practical Lower Bounds](https://mlsanity.com/paper/2111.10699/) (2021)
- [RAMA: A Rapid Multicut Algorithm on GPU](https://mlsanity.com/paper/2109.01838/) (2021)
- [FastDOG: Fast Discrete Optimization on GPU](https://mlsanity.com/paper/2111.10270/) (2021)
- [Learning to solve Minimum Cost Multicuts efficiently using Edge-Weighted Graph Convolutional Neural Networks](https://mlsanity.com/paper/2204.01366/) (2022)
- [ClusterFuG: Clustering Fully connected Graphs by Multicut](https://mlsanity.com/paper/2301.12159/) (2023)
- [Optimizing Edge Detection for Image Segmentation with Multicut Penalties](https://mlsanity.com/paper/2112.05416/) (2021)
- [Structured Prediction Problem Archive](https://mlsanity.com/paper/2202.03574/) (2022)
- [Uncertainty in Minimum Cost Multicuts for Image and Motion Segmentation](https://mlsanity.com/paper/2105.07469/) (2021)
- [M3C: A Framework towards Convergent, Flexible, and Unsupervised Learning of Mixture Graph Matching and Clustering](https://mlsanity.com/paper/2310.18444/) (2023)
- [Convergence of Some Convex Message Passing Algorithms to a Fixed Point](https://mlsanity.com/paper/2403.07004/) (2024)
- [Graph Neural Networks with Triangle-Based Messages for the Multicut Problem](https://mlsanity.com/paper/2605.13673/) (2026)

## Abstract (arXiv)

We propose a dual decomposition and linear program relaxation of the NP -hard minimum cost multicut problem. Unlike other polyhedral relaxations of the multicut polytope, it is amenable to efficient optimization by message passing. Like other polyhedral elaxations, it can be tightened efficiently by cutting planes. We define an algorithm that alternates between message passing and efficient separation of cycle- and odd-wheel inequalities. This algorithm is more efficient than state-of-the-art algorithms based on linear programming, including algorithms written in the framework of leading commercial software, as we show in experiments with large instances of the problem from applications in computer vision, biomedical image analysis and data mining.