The minimum cut problem asks to partition the nodes of an undirected weighted graph into two sets while minimizing the total weight of edges crossing the partition. Over recent years we have engineered a suite of fast algorithms for this task. Our current fastest exact algorithm combines an inexact solver to obtain a tighter bound, bound‑dependent reductions, improved data structures, and parallel contraction routines; it is released in the open‑source package VieCut and on real‑world graphs outperforms previous top solvers by up to 2.5× sequentially and up to 12.9× in parallel.
We introduce Agentic Algorithm Engineering (AAE), a methodology where autonomous large language model agents run the algorithm‑engineering cycle on an existing code base: they hypothesize where runtime is lost, implement changes, benchmark on a fixed instance set, and keep or discard the modification. Even after extensive manual tuning, the agent discovers substantial optimizations, especially on the DIMACS core instances: on real‑world k‑cores it gains 1.28× sequentially and 1.63× with 32 threads; on the DIMACS core set it improves by factors of 6.26 and 127 respectively.
Review