<p>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. </p>

<p>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: <a href="https://cstheory.stackexchange.com/questions/2312/max-cut-with-negative-weight-edges">Max-cut with negative weight edges</a></p>

CC BY-SA 3.0
2012-02-15T16:22:43.157Z
“Note that there is no PTAS for max-cut” requires the usual condition “unless P=NP.”
Tsuyoshi Ito
CC BY-SA 3.0
2011-12-08T03:19:09.533Z
2011-12-08T03:26:17.443Z
2017-04-13T12:32:28.080Z
Aaron Roth
<p>Unless $\epsilon$ is very large, it seems that no faster algorithms are known than the exact ones. For sparse graphs, the fastest one known seems to be one with running time $O(n+m) \min\{ 2^{m/5}, 2^{(m-n)/2}\}$ for a graph with $n$ vertices and $m$ edges: </p>

<p>Alexander D. Scott and Gregory B. Sorkin. Faster Algorithms for MAX CUT and MAX CSP, with Polynomial Expected Time for Sparse Instances. In Proc. APPROX/RANDOM 2003, LNCS 2764, pp.382--395, Springer, 2003. <a href="http://dx.doi.org/10.1007/978-3-540-45198-3_32" rel="nofollow">Link</a></p>

<p>The title refers to the fact that if the graph is a random graph (with edge probability $c/n$ for some $c \le 1$) then there is a polynomial expected time algorithm. </p>

CC BY-SA 3.0
2011-12-07T23:02:11.650Z
2011-12-07T23:02:11.650Z
Vincenzo
<p>As far as the approximation portion of your question goes... You can compute MAX-CUT with a 2 approximation in time $O(E)$ by using a simple randomized algorithm. For each edge in the graph flip a coin to determine which set to place it in. Output the larger of these two sets. In the worst case OPT will be E, and our randomized algorithm will be $|E|/2$. This is simple to see since each edge has 50% chance of being output in the cut. </p>

CC BY-SA 3.0
2011-12-07T04:44:58.977Z
I guess the questioner would like to know whether there is a better approximation than Goemans–Williamson (.878...) when the graph has O(n log n) edges.
Mahdi Cheraghchi
CC BY-SA 3.0
2011-12-07T05:33:38.383Z
thanks for the answer. As MCH mentions, I'm mainly interested in an $\epsilon$ approximation.
Dimitris
CC BY-SA 3.0
2011-12-08T03:15:06.670Z
I notice that the questioner is interested in graphs that have negative edge weights -- note that this simple algorithm does not work with negative edge weights.
Aaron Roth
CC BY-SA 3.0
2011-12-08T03:35:14.897Z
(And neither does the Goemans-Williamson algorithm...)
Aaron Roth
CC BY-SA 3.0
2011-12-07T04:28:48.317Z
2011-12-07T04:28:48.317Z
Nicholas Mancuso
<p>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.</p>

<p>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?</p>

CC BY-SA 3.0
2011-12-07T05:22:23.967Z
actually it's DENSE graphs on which MAX CUT is easy (i.e a PTAS exists). See for example http://www.cs.brown.edu/~ws/papers/maxcut.pdf
Suresh Venkat
CC BY-SA 3.0
2011-12-07T05:38:55.287Z
That's an interesting pointer. However, from a very fast diagonal parse on the paper, it seems that they don't consider weights; the authors say that "Previous algorithms for MaxCut have been extended to weighted instances when the weights define a metric. We conjecture that such instances can also be solved by an extension of our greedy algorithms."
Dimitris
CC BY-SA 3.0
2011-12-07T05:48:03.837Z
I see. there's older work on certain kinds of dense weighted MAX CUT: www.icsi.berkeley.edu/cgi-bin/pubs/publication.pl?ID=1121
Suresh Venkat
<cc.complexity-theory><optimization><max-cut>
Hardness of MAX-CUT on sparse graphs
Dimitris
# Hardness of MAX-CUT on sparse graphs

(Asked by: username_0 on 2011-12-07)

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?

**Tags:** cc.complexity-theory, optimization, max-cut
> **Comments:**
> **username_1**: actually it's DENSE graphs on which MAX CUT is easy (i.e a PTAS exists). See for example http://www.cs.brown.edu/~ws/papers/maxcut.pdf  
> **username_0**: That's an interesting pointer. However, from a very fast diagonal parse on the paper, it seems that they don't consider weights; the authors say that "Previous algorithms for MaxCut have been extended to weighted instances when the weights define a metric. We conjecture that such instances can also be solved by an extension of our greedy algorithms."  
> **username_1**: I see. there's older work on certain kinds of dense weighted MAX CUT: www.icsi.berkeley.edu/cgi-bin/pubs/publication.pl?ID=1121  

---

## 3 answers

### Answer by username_2 on 2011-12-08. Score: 8 | Accepted answer

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](https://cstheory.stackexchange.com/questions/2312/max-cut-with-negative-weight-edges)

> **Comments:**
> **username_3**: “Note that there is no PTAS for max-cut” requires the usual condition “unless P=NP.”  

---

### Answer by username_4 on 2011-12-07. Score: 3

Unless $\epsilon$ is very large, it seems that no faster algorithms are known than the exact ones. For sparse graphs, the fastest one known seems to be one with running time $O(n+m) \min\{ 2^{m/5}, 2^{(m-n)/2}\}$ for a graph with $n$ vertices and $m$ edges:

Alexander D. Scott and Gregory B. Sorkin. Faster Algorithms for MAX CUT and MAX CSP, with Polynomial Expected Time for Sparse Instances. In Proc. APPROX/RANDOM 2003, LNCS 2764, pp.382--395, Springer, 2003. [Link](http://dx.doi.org/10.1007/978-3-540-45198-3_32)

The title refers to the fact that if the graph is a random graph (with edge probability $c/n$ for some $c \le 1$) then there is a polynomial expected time algorithm.


---

### Answer by username_5 on 2011-12-07. Score: 0

As far as the approximation portion of your question goes... You can compute MAX-CUT with a 2 approximation in time $O(E)$ by using a simple randomized algorithm. For each edge in the graph flip a coin to determine which set to place it in. Output the larger of these two sets. In the worst case OPT will be E, and our randomized algorithm will be $|E|/2$. This is simple to see since each edge has 50% chance of being output in the cut.

> **Comments:**
> **username_6**: I guess the questioner would like to know whether there is a better approximation than Goemans–Williamson (.878...) when the graph has O(n log n) edges.  
> **username_0**: thanks for the answer. As MCH mentions, I'm mainly interested in an $\epsilon$ approximation.  
> **username_2**: I notice that the questioner is interested in graphs that have negative edge weights -- note that this simple algorithm does not work with negative edge weights.  
> **username_2**: (And neither does the Goemans-Williamson algorithm...)  

---

