35
$\begingroup$

Let $G = (V, E, w)$ be a graph with weight function $w:E\rightarrow \mathbb{R}$. The max-cut problem is to find: $$\arg\max_{S \subset V} \sum_{(u,v) \in E : u \in S, v \not \in S}w(u,v)$$ If the weight function is non-negative (i.e. $w(e) \geq 0$ for all $e \in E$), then there are many extremely simple 2-approximations for max-cut. For example, we can:

  1. Pick a random subset of vertices $S$.
  2. Pick an ordering on the vertices, and greedily place each vertex $v$ in $S$ or $\bar{S}$ to maximize the edges cut so far
  3. Make local improvements: If there is any vertex in $S$ that can be moved to $\bar{S}$ to increase the cut (or vice versa), make the move.

The standard analysis of all of these algorithms actually shows that the resulting cut is at least as large as $\frac{1}{2}\sum_{e \in E}w(e)$, which is an upper bound on $1/2$ the weight of the max-cut if $w$ is non-negative -- but if some edges are allowed to have negative weight, is not!

For example, algorithm 1 (pick a random subset of vertices) can clearly fail on graphs with negative edge weights.

My question is:

Is there a simple combinatorial algorithm that gets an O(1) approximation to the max-cut problem on graphs that can have negative edge weights?

To avoid the possibly sticky issue of the max-cut taking value $0$, I will allow that $\sum_{e \in E}w(e) > 0$, and/or be satisfied with algorithms that result in small additive error in addition to a multiplicative factor approximation.

$\endgroup$
  • 1
    $\begingroup$ Is the condition "simple combinatorial" essential here? $\endgroup$ – Hsien-Chih Chang 張顯之 Oct 20 '10 at 3:06
  • $\begingroup$ I'm most interested in a simple, combinatorial algorithm like the 2-approximations for the positive weight case. Note that I am asking about any O(1) approximation, so I would expect that if any algorithm can achieve this, it should be possible with a simple one. But I would also be interested in what performance guarantees are for SDP algorithms on graphs with negative edge weights, or evidence that no constant-factor approximation algorithm exists if $P \ne NP$. $\endgroup$ – Aaron Roth Oct 20 '10 at 3:09
28
$\begingroup$

Here was my first attempt at an argument. It was wrong, but I fixed it after the "EDIT:"

If you could efficiently approximately solve the max-cut problem with negative edge weights, couldn't you use that to solve the max-cut problem with positive edge weights? Start with a max-cut problem you want to solve whose optimal solution is $b$. Now, put a large negative weight edge (with weight $-a$) between $u$ and $v$. The optimum solution of the new problem is $b-a$, so our hypothetical approximation algorithm will get you a solution with maximum cut whose value is at most $(b-a)/2$ worse than optimal. On the original graph, the maximum cut is still at most $(b-a)/2$ worse than optimal. If you choose $a$ close to $b$, this violates the inapproximability result that if P$\neq$NP, you cannot approximate max-cut to better than a $16/17$ factor.

EDIT:

The above algorithm doesn't work because you can't guarantee that $u$ and $v$ are on opposite sides of the cut in the new graph, even if they were originally. I can fix this as follows, though.

Let's assume that we have an approximation algorithm which will give us a cut within a factor of 2 of OPT as long as the sum of all the edge weights are positive.

As above, start with a graph $G$ with all non-negative weights on edges. We'll find a modified graph $G^* $ with some negative weights such that if we can approximate the max cut of $G^* $ within a factor of 2, we can approximate the max cut of $G$ very well.

Choose two vertices $u$ and $v$, and hope that they're on opposite sides of the max cut. (You can repeat this for all possible $v$ to ensure that one try works.) Now, put a large negative weight $-d$ on all edges $(u,x)$ and $(v,x)$ for $x \neq u,v$, and a large positive weight $a$ on edge $(u,v)$. Assume that the optimal cut has weight $OPT$.

A cut with value $c$ in $G$, where vertices $u$ and $v$ are on the same side of the cut, now has value at $c - 2dm$ where $m$ is the number of vertices on the other side of the cut. A cut with $(u,v)$ on opposite sides with original value $c$ now has value $c + a - (n-2)d$. Thus, if we choose $d$ large enough, we can force all cuts with $u$ and $v$ on the same side to have negative value, so if there is any cut with positive value, then the optimal cut in $G^* $ will have $u$ and $v$ on opposite sides. Note that we are adding a fixed weight $(a - (n-2)d)$ to any cut with $u$ and $v$ on opposite sides.

Let $f=(a - (n-2)d)$. Choose $a$ so that $f \approx - 0.98 OPT$ (we'll justify this later). A cut with weight $c$ in $G$ having $u$ and $v$ on opposite sides now becomes a cut with weight $c - 0.98 OPT$. This means the optimal cut in $G^* $ has weight $0.02 OPT$. Our new algorithm finds a cut in $G^* $ with weight at least $0.01 OPT$. This translates into a cut in the original graph $G$ with weight at least $0.99OPT$ (since all cuts in $G^* $ with positive weight separate $u$ and $v$), which is better than the inapproximability result.

There is no problem with choosing $d$ large enough to make any cut with $u$ and $v$ on the same side negative, since we can choose $d$ as large as we want. But how did we choose $a$ so that $f \approx -.99OPT$ when we didn't know $OPT$? We can approximate $OPT$ really well ... if we let $T$ be the sum of the edge weights in $G$, we know $\frac{1}{2}T \leq OPT \leq T$. So we have a fairly narrow range of values for $f$, and we can iterate over $f$ taking all values between $-.49T$ and $-.99T$ at intervals of $0.005T$. For one of these intervals, we are guaranteed that $f \approx -0.98 OPT$, and so one of these iterations is guaranteed to return a good cut.

Finally, we need to check that the new graph has edge weights whose sum is positive. We started with a graph whose edge weights had sum $T$, and added $f$ to the sum of the edge weights. Since $-.99T \leq f \leq -.49T$, we're O.K.

$\endgroup$
  • 1
    $\begingroup$ But what are your $u$ and $v$? The usual formulation of the max-cut problem does not have any "special nodes" that need to be separated. $\endgroup$ – Jukka Suomela Oct 19 '10 at 22:45
  • 3
    $\begingroup$ Hi Ian -- I don't think that works though. Why do there necessarily have to exist any $u$ and $v$ that are separated by the max-cut in the original graph, and remain separated by the max-cut after a heavy negative edge is added between them? Consider for example the complete graph -- adding a single, arbitrarily negative edge anywhere does not change the cut value at all. $\endgroup$ – Aaron Roth Oct 20 '10 at 0:57
  • 2
    $\begingroup$ One issue is that if you add a negative edge between every pair of vertices, then you are modifying the value of different cuts by different amounts. (We subtract, say, $|S|\cdot|\bar{S}|\cdot a$ from the value of cut $S$). So we have the problem that the identity of the max-cut in the modified graph does not necessarily correspond to the max-cut in the original graph. $\endgroup$ – Aaron Roth Oct 20 '10 at 1:18
  • 1
    $\begingroup$ @Peter: In the paragraph after the one I quoted you choose $a$ sufficiently small to make $f \approx -0.98 OPT$. You can't safely choose $a$ to be sufficiently large in one paragraph and sufficiently small in the next! In particular, there is no way to choose $a$ and $d$ to ensure that $c+a-(n-2)d>c-dm$ for all $0\le m \le n$ and simultaneously have $a-(n-2)d = f\approx -0.98 \cdot OPT$. This follows because $c+a-(n-2)d>c-dm$ for all $0\le m \le n$ implies that $f=a-(n-2)d > 0$. $\endgroup$ – Warren Schudy Oct 20 '10 at 23:02
  • 2
    $\begingroup$ @Warren, You choose $d$ large enough so that $c-dm<0$ for all cuts. This can be done by choosing $d$ sufficiently large. You then choose $a$ the right size so that the optimal cut is just barely above $0$. Read the last two paragraphs of my answer. $\endgroup$ – Peter Shor Oct 21 '10 at 1:18
11
$\begingroup$

In the article "Approximate Max Cut" by S. Har-Peled, the last line of the paper mentioned that the real weighted version of max-cut has been discussed in

Approximating the cut-norm via grothendieck’s inequality, Noga Alon and Assaf Naor, SIAM Journal on Computing, 2006.

It is indeed an SDP algorithm, and it seems to me that the approximation ratio is 0.56, though I'm not sure if the reduction discussed in the paper is ratio preserving. Maybe a deeper look into the paper will help!

$\endgroup$
  • $\begingroup$ the problem in Alon-Naor is similar but I don't think there is a ratio preserving reduction. their problem is to maximize $x^TMy$ where $x, y \in \{\pm 1\}^n$ and $M$ is an $n \times n$ matrix. for max-cut and its close relatives it's crucial that $x = y$ $\endgroup$ – Sasho Nikolov Aug 14 '12 at 18:25
  • $\begingroup$ @SashoNikolov: for the cut norm it's immaterial, up to constant factors, whether we demand $x=y$ or not. $\endgroup$ – david Dec 10 '13 at 10:36
  • $\begingroup$ @david I know this reduction, but the statement that's actually true is that $\max_x |x^TMx| \leq \max_{x, y}{x^TMy} \leq 4 \max_x |x^TMx|$ where all maximums are over $\{-1, 1\}^n$, and $M$ is symmetric with nonnegative diagonal. However, the problem $\max_x |x^TMx|$ can have very different value from $\max_x x^TMx$ (which is what we need for MaxCut). For example, consider $M = I-J$, where $J$ is the $n\times n$ all ones matrix. You can see $\max_{x}{x^TMx}$ is about $n/2$, while $\max_{x}{|x^TMx|}$ is $n^2 - n$. $\endgroup$ – Sasho Nikolov Dec 10 '13 at 16:13
6
$\begingroup$

Your problem has a logarithmic approximation by reduction to a quadratic programming problem.

The MaxQP problem is the problem of approximating the quadratic form $x^TMx$ for a $n \times n$ matrix $M$, where $x$ ranges over $\{\pm 1\}^n$. MaxCut can be written in this form by setting $M = \frac{1}{2n}(\sum{w_e})I - \frac{1}{2}A$ where $I$ is the identity matrix and $A$ is the adjacency matrix. The MaxQP algorithm of Charikar and Wirth gives an $O(\log n)$ approximation for MaxQP as long as $M$ has a non-negative diagonal. So as long as $\sum{w_e} \geq 0$, MaxCut with negative weights has a logarithmic approximation.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.