Skip to content

VieCut v2.0

Latest

Choose a tag to compare

@schulzchristian schulzchristian released this 17 Nov 13:55
ad4e697

What's New

The speedups in this release were found with Agentic Algorithm Engineering (AAE): paper, code and methodology.

  • Exact minimum cut 8.9x faster on one thread and 8.8x faster on 32 threads (geometric mean over a 53-instance benchmark), with every computed cut unchanged. Applies to mincut_parallel exact and mincut noi.
  • Large-cut instances no longer run out of memory: the priority queue is selected by the cut value, so the parallel exact path no longer builds bucket queues sized by the cut (previously hundreds of GiB on large-cut graphs).
  • In-place contraction instead of rebuilding the graph every round, plus a parallel dense contraction for rounds that collapse the graph hard.
  • One CAPFOREST pass per thread, dropping a feedback rule that collapsed to a single pass.
  • Cascading Padberg-Rinaldi reduction (pr_cascade) that contracts on the spot and re-reads degrees.
  • Lighter inner loops: smaller edge record under COMPACT_EDGES, a lighter traversal loop, and stamp-array shared-neighbourhood lookups in the contraction primitives.
  • Skips the heuristic pre-run where the minimum degree already is the cut.
  • New tool graph2bin: converts METIS graphs to a binary format that graph_io reads transparently.
  • Stoer-Wagner fixed and available as mincut <graph> sw (fix by Bora Uçar): it previously returned wrong cuts or crashed. It now computes the cut value and, with -s, the cut itself, and is tested against brute force on random weighted graphs.
  • Build fixes: builds with CMake 4, the parallel test binaries compile again, the parallel cactus with -s keeps the cut sides on multiple threads, and the bundled googletest builds on GCC 11 and newer.
  • No existing interface changed. See the one-page summary and the AAE paper.