Agentic method speeds up graph minimum cut algorithms greatly
Agentic Algorithm Engineering: Improving Shared-Memory Exact Minimum Cuts
Artificial Intelligence
Summary
The minimum cut problem involves splitting a network's nodes into two groups to minimize the total weight of the edges cut between them. The authors built a very fast algorithm for this problem, using both exact and inexact methods together with clever data structures and parallel computations. They introduced a new approach called agentic algorithm engineering, where autonomous AI agents improve the code by testing ideas automatically. These agents found big improvements, speeding up the algorithm more than manual tuning had achieved before.
What this means in practice
- •For network infrastructure engineers: Optimize network partitioning tasks by using faster minimum cut computations for better load balancing and fault detection.
- •For data center operators: Improve parallel processing of large graph datasets for system reliability and resource management via enhanced exact minimum cut algorithms.
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.