mlsanityData to 14 Oct 2026

Agentic Algorithm Engineering: Improving Shared-Memory Exact Minimum Cuts

arXiv 2609.07204 ↗First posted 7 Sep 2026cs.AI cs.DC cs.DScited by 0

On the map: LLM agents and tool use → General LLM agent frameworks and benchmarks

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.

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.

Builds on

11 of 46 references.

References · 11

  1. 2025AlphaEvolve: A coding agent for scientific and algorithmic discoverycited by 867
  2. 2024Deterministic Near-Linear Time Minimum Cut in Weighted Graphscited by 3
  3. 2014Deterministic Edge Connectivity in Near-Linear Timecited by 2
  4. 2019Faster Algorithms for Edge Connectivity via Random 2-Out Contractionscited by 2
  5. 2021Deterministic Mincut in Almost-Linear Timecited by 2
  6. 2017Practical Minimum Cut Algorithmscited by 1
  7. 2018Shared-memory Exact Minimum Cutscited by 1
  8. 2021Deterministic Min-cut in Poly-logarithmic Max-flowscited by 1
  9. 2024Engineering Weighted Connectivity Augmentation Algorithmscited by 1
  10. 2024The Complexity of Manipulation of k-Coalitional Games on Graphscited by 1
  11. 2025On the Optimization of Methods for Establishing Well-Connected Communitiescited by 1

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2025CO-Bench: Benchmarking Language Model Agents in Algorithm Search for Combinatorial Optimization
  2. 2026Codebook Agent: Amortized Topology Design for LLM Multi-Agent Systems
  3. 2025FormulaOne: Measuring the Depth of Algorithmic Reasoning Beyond Competitive Programming
  4. 2026GraphDC: A Divide-and-Conquer Multi-Agent System for Scalable Graph Algorithm Reasoning
  5. 2026AgentSlimming: Towards Efficient and Cost-Aware Multi-Agent Systems
  6. 2026MAS-Algorithm: A Workflow for Solving Algorithmic Programming Problems with a Multi-Agent System
  7. 2026Problem Reductions at Scale: Agentic Integration of Computationally Hard Problems
  8. 2026GTA: Graph Theory Agent and Benchmark for Algorithmic Graph Reasoning with LLMs