Optimal sampling size found for estimating maximum graph cuts
Optimal Sample Complexity for Max-Cut
Data Structures and Algorithms
Summary
Finding the largest cut in a network, called Max-Cut, is a complex problem. This paper finds the smallest number of nodes you need to sample randomly to estimate the Max-Cut value well. The authors show that sampling about 1 over epsilon squared nodes is enough to get a close estimate, improving on previous higher bounds. Their results also cover cases where nodes are sampled by their importance and extend to similar problems with more parts or weighted edges.
What this means in practice
- •For network analysts: Estimate large network partitions quickly by sampling a minimal subset of nodes to approximate maximum cuts with guaranteed accuracy.
- •For data scientists: Use minimal vertex sampling to approximate graph clustering objectives when working with large weighted graphs efficiently.
A theory result. No direct application yet.
Authors
Itamar Bender, Robert Krauthgamer
Abstract
We determine the optimal sample size for constructing value coresets for Max-Cut via uniform vertex sampling. That is, sampling $O(\varepsilon^{-2})$ 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 $\varepsilon n^2$-approximation to that of the original graph, with constant success probability. This improves the previously known $O(\varepsilon^{-4})$ 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(\varepsilon^{-2})$ vertices yields $(1\pm\varepsilon)$-approximation to the Max-Cut value, and to Max-Cut in graphs with edge weights in $[0,1]$ and average weighted degree $\bar d$, achieving the same $(1\pm\varepsilon)$-approximation by either uniform or importance sampling of $O(\varepsilon^{-2}n/\bar d)$ vertices. We additionally show how to use this coreset to recover a cut of expected value at least $OPT-\varepsilon n^2$, by making $O(n\varepsilon^{-2})$ additional edge-weight queries. Finally, our result extends to Max-$r$-Cut, giving an additive $\varepsilon n^2$-approximation using a sample of $O(\varepsilon^{-2}\log(2r))$ vertices.