(This is a cross-post from the Theoretical Computer Science Stack Exchange.)

For the purposes of this question, a cut in a graph $G$ is the edge-set $\delta (S)\subseteq E(G)$ between some vertex-set $S$ and its complement. A max cut is one with at least as many edges as any other cut. Finding a max cut is NP-hard, but a greedy algorithm (e.g.) can approximate a max cut, finding a cut with at least half as many edges as possible.

Equivalently, a cut $\delta (S)\subseteq E(G)$ is a max cut if and only if $$| \delta (S)\cap \delta (T) |\geq \frac{1}{2}|\delta (T)| \qquad \forall\text{ cuts } \delta (T)\subseteq E(G).$$ Proof: It should be clear that the standard definition implies this one. To show that these inequalities imply $\delta (S)$ is at least as big as any other cut $\delta (S')$, observe that $$|\delta (S)| - |\delta (S')| = |\delta (S) \cap \delta (S\Delta S')| - |\delta (S') \cap \delta (S\Delta S')|.$$ Because the two edge-sets appearing in the right-hand side partition the edges of the cut $\delta (S\Delta S')$, applying the above inequality with $S\Delta S'$ in the role of $T$ gives $|\delta (S)|-|\delta (S')|\geq 0$. $\square$

I'd like to know whether max cuts can be easily approximated in the sense of my second definition. Specifically:

Question: Is there a polynomial-time algorithm to find a cut $\delta (S)\subseteq E(G)$ with $$| \delta (S)\cap \delta (T) |\geq \epsilon |\delta (T)| \qquad \forall\text{ cuts } \delta (T)\subseteq E(G)$$ for some $\epsilon > 0$?

  • $\begingroup$ Hi, Ross, what is the relationship between $S$ and $T$? $\endgroup$ – Rupei Xu May 11 '15 at 8:32
  • $\begingroup$ The object of the algorithm is to find $S$. I would like $S$ to have the property such that, for every other vertex-set $T\subseteq V(G)$, the cut associated with $S$ contains at least an $\epsilon$-fraction of the edges in the cut associated with $T$. $\endgroup$ – Ross Churchley May 11 '15 at 22:20

Your Answer

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

Browse other questions tagged or ask your own question.