Let a weighted graph $G(V,E)$, where the weights are real (positve and negative). Assume that $G$ has $\mathcal{O}(n\log n)$ edges.How fast can we compute MAX-CUT on this graph?Can we compute (approximate within $\epsilon$) MAXCUT faster on sparse graphs compared to dense ones?
Hardness of MAX-CUT on sparse graphs
cc.complexity theory;optimization;max cut
There cannot be significantly better algorithms for graphs with $O(n\log n)$ edges than there are for general graphs. This is because the Benczur-Karger cut sparsifier can take an arbitrary graph, and output a graph with only $O(\frac{n\log n}{\epsilon})$ edges such that the value of any cut in the sparsified graph is within a $(1\pm\epsilon)$ factor of the cut value in the original graph. Therefore, a PTAS for sparse graphs would yield a PTAS for general graphs, by simply first running the cut sparsifier, and then approximating max-cut in the sparse graph. Since it is NP hard to approximate max cut in general graphs to within a factor of 16/17, this is also true for sparse graphs. Note that there is no PTAS for max-cut even when all edge weights are non-negative. Things are even worse when negative edge weights are allowed, as in your question. See this question for the negative edge weight case: Max-cut with negative weight edges