# Agentic Algorithm Engineering: Improving Shared-Memory Exact Minimum Cuts

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in General LLM agent frameworks and benchmarks, one of 16 directions in LLM agents and tool use.
- Builds on 11 of its 46 references that are in the map.
- First posted on arXiv 7 Sep 2026.

## Placed in

- LLM agents and tool use / [General LLM agent frameworks and benchmarks](https://mlsanity.com/agents/general-llm-agent-frameworks-and-benchmarks/)

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

- [AlphaEvolve: A coding agent for scientific and algorithmic discovery](https://mlsanity.com/paper/2506.13131/) (2025)
- [Deterministic Near-Linear Time Minimum Cut in Weighted Graphs](https://mlsanity.com/paper/2401.05627/) (2024)
- [Deterministic Edge Connectivity in Near-Linear Time](https://mlsanity.com/paper/1411.5123/) (2014)
- [Faster Algorithms for Edge Connectivity via Random 2-Out Contractions](https://mlsanity.com/paper/1909.00844/) (2019)
- [Deterministic Mincut in Almost-Linear Time](https://mlsanity.com/paper/2106.05513/) (2021)
- [Practical Minimum Cut Algorithms](https://mlsanity.com/paper/1708.06127/) (2017)
- [Shared-memory Exact Minimum Cuts](https://mlsanity.com/paper/1808.05458/) (2018)
- [Deterministic Min-cut in Poly-logarithmic Max-flows](https://mlsanity.com/paper/2111.02008/) (2021)
- [Engineering Weighted Connectivity Augmentation Algorithms](https://mlsanity.com/paper/2402.07753/) (2024)
- [The Complexity of Manipulation of k-Coalitional Games on Graphs](https://mlsanity.com/paper/2408.07368/) (2024)
- [On the Optimization of Methods for Establishing Well-Connected Communities](https://mlsanity.com/paper/2509.02590/) (2025)

## Abstract (arXiv)

The minimum cut problem for an undirected edge-weighted graph asks us to divide its set of nodes into two blocks while minimizing the weighted sum of the cut edges. Over the last years, we engineered a range of fast algorithms for this problem. Our fastest exact algorithm uses an inexact algorithm to obtain a better bound for the problem, reductions that depend on this bound, improved data structures and parallel contraction routines. It is available in the open-source package VieCut and, on real-world instances, outperformed the previously fastest solvers by a factor of up to 2.5 sequentially and up to 12.9 when run in parallel. We improve this algorithm using agentic algorithm engineering (AAE), a methodology that we introduce here, in which autonomous large language model agents run the algorithm engineering cycle on an existing code base: they form hypotheses about where running time is lost, implement them, benchmark the result on a fixed instance set and keep or discard the change. Even though we had already tuned our algorithm by hand extensively, the agent finds significant optimizations, in particular on the DIMACS core instances: factors of 1.28 (sequential) and 1.63 (32 threads) on real-world k-cores, and 6.26 and 127 on the DIMACS core instances.