Module approximate 

Approximate Min-Cut for All Cut Sizes

Implementation based on “Approximate Min-Cut in All Cut Sizes” (SODA 2025, arXiv:2412.15069).

Key Innovation

Uses spectral sparsification with edge sampling to achieve (1+ε)-approximate minimum cuts for ANY cut size, not just small cuts.

Time Complexity

• Preprocessing: O(m log² n / ε²)
• Query: O(n polylog n / ε²)

Algorithm Overview

1. Compute effective resistances for all edges
2. Sample edges with probability proportional to resistance × weight
3. Build sparsifier with O(n log n / ε²) edges
4. Run exact min-cut on sparsifier (feasible due to small size)

Structs

ApproxMinCut

Approximate minimum cut for all cut sizes

ApproxMinCutConfig

Configuration for approximate min-cut

ApproxMinCutResult

Result of approximate min-cut query

ApproxMinCutStats

Statistics for approximate min-cut