MAX-CUT on Samplings of Dense Graphs

The maximum cut problem finds a partition of a graph that maximizes the number of crossing edges. When the graph is dense or is sampled based on certain planted assumptions, there exist polynomial-time approximation schemes that given a fixed
$\epsilon > 0$
., find a solution whose value is at least
$1-\epsilon$
of the optimal value. This paper presents another random model relating to both successful cases. Consider an n-vertex graph
$G$
whose edges are sampled from an unknown dense graph
$H$
independently with probability
$p=\Omega(1/\sqrt{\log n});$
this input graph
$G$
has
$O(n^{2}/\sqrt{\log n})$
edges and is no longer dense. We show how to modify a PTAS by de la Vega for dense graphs to find an
$(1-\epsilon)$
-approximate solution for
$G$
. Although our algorithm works for a very narrow range of sampling probability
$p$
, the sampling model itself generalizes the planted models fairly well.