Optimal Sample Complexity for Max-Cut

We determine the optimal sample size for constructing value coresets for Max-Cut via uniform vertex sampling. That is, sampling O(ε⁻²) vertices uniformly at random in n-vertex graphs with edge weights in $[0,1]$ yields a reweighted subgraph whose Max-Cut value is an additive ε n²-approximation to that of the original graph, with constant success probability. This improves the previously known O(ε⁻⁴) upper bound and matches the known lower bound. The same guarantee holds also for importance sampling, where vertices are sampled proportionally to their weighted degrees, and we further prove a matching lower bound for this sampling method. Our analysis extends directly to metric Max-Cut, showing that importance sampling of O(ε⁻²) vertices yields (1±ε)-approximation to the Max-Cut value, and to Max-Cut in graphs with edge weights in $[0,1]$ and average weighted degree d, achieving the same (1±ε)-approximation by either uniform or importance sampling of O(ε⁻²n/ d) vertices. We additionally show how to use this coreset to recover a cut of expected value at least OPT-ε n², by making O(nε⁻²) additional edge-weight queries. Finally, our result extends to Max-r-Cut, giving an additive ε n²-approximation using a sample of O(ε⁻²log(2r)) vertices.