Max-k-cut with negative edge weights

Question

Let $G=(V,E,w)$ be a graph and for edge $e\in E$, there is associated weight $w_e$. The max-k-cut wants to partition V into k subsets $P_1,\cdots,P_k$ and maximize $\sum_{1\leq r<s\leq k}\sum_{i\in P_r,j\in P_s}w_{ij}$.

If $k=2$, or we assume non-negative weights, there is $O(1)$-approximation algorithms. I am wondering if we can get $O(1)$ or logarithmic approximation for general $k$ and possibly negative weights.

Besides, I am more interested in the case where the objective is to maximize $|\sum_{1\leq r<s\leq k}\sum_{i\in P_r,j\in P_s}w_{ij}|$.

Answer 1

There is no approximation algorithm for the problem of maximizing $\sum_{(i,j)\text{ is cut}} w_{ij}$, since it's even NP-hard to determine whether the optimal value is positive. However, there is a constant-factor approximation algorithm for the problem of maximizing $\left|\sum_{(i,j)\text{ is cut}} w_{ij}\right|$. I will briefly describe how this algorithm works.

I. For a fixed instance of the problem, let $OPT_k$ be the optimal value when we partition $V$ into $k$ parts $P_1, \dots, P_k$. We assume that some parts may be empty. We now show that $$OPT_k/2 \leq OPT_2 \leq OPT_k.$$

• Let $(P_1, P_2)$ be an optimal solution with 2 parts. Pad this partition with $k-2$ empty parts. The value of the obtained solution $(P_1, P_2, \varnothing, \dots, \varnothing)$ is $OPT_2$. Thus, $OPT_k \geq OPT_2$.
• Now consider an optimal solution $(P_1, \dots, P_k)$ for $k$ parts. Randomly divide all clusters in two groups. Let $P_1'$ be the union of parts in the first group; $P_2'$ be the union of groups in the second. It's easy to see that $${\mathbb E}\left[\sum_{(i,j)\text{ is cut by }(P_1', P_2')} w_{ij}\right] = \frac12 \sum_{(i,j)\text{ is cut by }(P_1,\dots, P_k)} w_{ij}.$$ Therefore, $${\mathbb E}\left[\left|\sum_{(i,j)\text{ is cut by }(P_1', P_2')} w_{ij}\right|\right] \geq \left|\frac12 \sum_{(i,j)\text{ is cut by }(P_1,\dots, P_k)} w_{ij}\right|.$$ We conclude that $OPT_k \geq OPT_2/2$.

Thus, it is sufficient to design an approximation algorithm for $OPT_2$.

II. Recall that the Grothendieck inequality states that $$\max_{x,y\in\{-1,1\}^n} \sum_{i,j}w_{ij} x_i y_j \geq \frac{1}{K} \max_{\text{unit vectors }u_1,\dots,u_n,v_1,\dots, v_n} \sum_{i,j}w_{ij} \langle u_i, v_j\rangle$$ where $K$ is an absolute constant. Using semidefinite programming and the Grothendieck inequality, we can get a constant factor approximation for the following Quadratic Programming problem [Alon and Naor 2004].

$$\max_{x,y\in\{-1,1\}^n} \sum_{i,j}w_{ij} x_i y_j$$

The same algorithm gives a constant factor approximation for $\max_{z\in\{-1,1\}^n} \left|\sum_{i,j}w_{ij} z_i z_j\right|$ (we first find $x$ and $y$ and then output the better of the two solutions $z=x$ and $z=y$).

III. Let $W = \sum_{i<j}w_{ij}$ and $$QP= \max_{z\in\{-1,1\}^n} \left|\sum_{i<j}w_{ij} z_i z_j\right|=\max_{z\in\{-1,1\}^n} \left|W -2\sum_{\substack{i<j\\z_iz_j=-1}}w_{ij}\right|.$$ Note that there is one-to-one correspondence between solutions to the QP and the partitioning problem; namely, a solution $z_1,\dots,z_n$ defines the following partition $P_1 = \{i:z_i=1\}$ and $P_2=\{i:z_i = -1\}$.

If solution $(P_1, P_2)$ has value $x$ then the value of the corresponding QP solution is either $|W-2x|=|2x-W|$ or $\left|2x + W\right|$. It follows that $|OPT_2- 2QP| \leq |W|$.

IV. Now we solve the QP approximately, obtain a solution $z_1',\dots, z_n'$, and output the better of the following two solution:

• partition $(P_1', P_2')$ defined by the QP solution $z_1', \dots, z_n'$; the value of this solution is $\Theta(OPT_2) - O(|W|)$.
• a random partition; the expected value of this solution is at least $|W|/2$.

It's easy to see that this algorithm gives a constant factor approximation for the partitioning problem.