MAX-CUT on Samplings of Dense Graphs
Jittat Fakcharoenphol, Phanu Vajanopath · 2022
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.