5
$\begingroup$

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

$\endgroup$
  • $\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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.