Improving minimum cut algorithms with AI agents for faster graph splitting
Agentic Algorithm Engineering: Improving Shared-Memory Exact Minimum Cuts
Artificial Intelligence
Summary
Dividing a network into two parts by cutting the fewest possible connections is a problem that people study a lot, especially when the connections have different strengths. The authors worked on making programs that solve this problem faster and better. They introduced a new way where AI agents, powered by large language models, test and improve the program automatically by guessing where it slows down and fixing those parts. This approach surprisingly improved their already well-tuned program, speeding it up by large factors on important test cases. Their method shows how AI can help improve complex algorithms even beyond what experts have done by hand.
Minimum cutGraph theoryEdge weightsAlgorithm engineeringParallel computingLarge language modelsAgentic algorithm engineeringBenchmarkingOpen source softwareDIMACS benchmarks
Authors
David A. Bader, Adil Chhabra, Ernestine Großmann, Monika Henzinger, Alexander Noe, Christian Schulz
Abstract
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.