8
$\begingroup$

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).$$ (Sidenote: 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$.)

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$?

$\endgroup$

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.