 Maximum cut

For a graph, a maximum cut is a cut whose size is at least the size of any other cut. The problem of finding a maximum cut in a graph is known as the maxcut problem.
The problem can be stated simply as follows. One wants a subset S of the vertex set such that the number of edges between S and the complementary subset is as large as possible.
There is a more advanced version of the problem called weighted maxcut. In this version each edge has a real number, its weight, and the objective is to maximize not the number of edges but the total weight of the edges between S and its complement. The weighted maxcut problem is often, but not always, restricted to nonnegative weights, because negative weights can change the nature of the problem.
Contents
Computational complexity
The following decision problem related to maximum cuts has been studied widely in theoretical computer science:
 Given a graph G and an integer k, determine whether there is a cut of size at least k in G.
This problem is known to be NPcomplete. It is easy to see that problem is in NP: a yes answer is easy to prove by presenting a large enough cut. The NPcompleteness of the problem can be shown, for example, by a transformation from maximum 2satisfiability (a restriction of the maximum satisfiability problem).^{[1]} The weighted version of the decision problem was one of Karp's 21 NPcomplete problems;^{[2]} Karp showed the NPcompleteness by a reduction from the partition problem.
The canonical optimization variant of the above decision problem is usually known as the maximum cut problem or maxcut problem and is defined as:
 Given a graph G, find a maximum cut.
Polynomialtime algorithms
As the maxcut problem is NPhard, no polynomialtime algorithms for maxcut in general graphs are known. However, a polynomialtime algorithm to find maximum cuts in planar graphs exists.^{[3]}
Approximation algorithms
There is a simple randomized 0.5approximation algorithm: for each vertex flip a coin to decide to which half of the partition to assign it.^{[4]}^{[5]} In expectation, half of the edges are cut edges. This algorithm can be derandomized with the method of conditional probabilities; therefore there is a simple deterministic polynomialtime 0.5approximation algorithm as well.^{[6]}^{[7]} One such algorithm is: given a graph G = (V,E) start with an arbitrary partition of V and move a vertex from one side to the other if it improves the solution until no such vertex exists. The number of iterations is bound by because the algorithm improves the cut value by at least 1 at each step and the maximum cut is at most . When the algorithm terminates, each vertex has at least half its edges in the cut (otherwise moving v to the other subset improves the solution). Therefore the cut is at least .
The best known maxcut algorithm is the 0.878…approximation algorithm by Goemans and Williamson using semidefinite programming and randomized rounding.^{[8]}^{[9]} It has been shown by Khot et al that this is the best possible approximation ratio for MaxCut assuming the unique games conjecture.
Inapproximability
The maxcut problem is APXhard,^{[10]} meaning that there is no polynomialtime approximation scheme (PTAS), arbitrarily close to the optimal solution, for it, unless P = NP. Moreover, it has been shown NPhard to approximate the maxcut value to better than 16 / 17 = 0.941….^{[11]}^{[12]}
Assuming the unique games conjecture (UGC), it is in fact NPhard to approximate the maxcut value by a factor of for any , where α_{GW} = 0.878… is the approximation factor of Goemans–Williamson.^{[13]} In other words, assuming the UGC and that , the Goemans–Williamson algorithm yields essentially the best polynomialtimecomputable possible approximation ratio for the problem.
Maximum bipartite subgraph
A cut is a bipartite graph. The maxcut problem is essentially the same as the problem of finding a bipartite subgraph with the most edges.
Let G = (V,E) be a graph and let H = (V,X) be a bipartite subgraph of G. Then there is a partition (S, T) of V such that each edge in X has one endpoint in S and another endpoint in T. Put otherwise, there is a cut in H such that the set of cut edges contains X. Therefore there is a cut in G such that the set of cut edges is a superset of X.
Conversely, let G = (V,E) be a graph and let X be a set of cut edges. Then H = (V,X) is a bipartite subgraph of H.
In summary, if there is a bipartite subgraph with k edges, there is a cut with at least k cut edges, and if there is a cut with k cut edges, there is a bipartite subgraph with k edges. Therefore the problem of finding a maximum bipartite subgraph is essentially the same as the problem of finding a maximum cut.^{[14]} The same results on NPhardness, inapproximability and approximability apply to both the maximum cut problem and the maximum bipartite subgraph problem.
See also
Notes
 ^ Garey & Johnson (1979).
 ^ Karp (1972).
 ^ Hadlock (1975).
 ^ Mitzenmacher & Upfal (2005), Sect. 6.2.
 ^ Motwani & Raghavan (1995), Sect. 5.1.
 ^ Mitzenmacher & Upfal (2005), Sect. 6.3.
 ^ Khuller, Raghavachari & Young (2007).
 ^ Gaur & Krishnamurti (2007).
 ^ Ausiello et al. (2003)
 ^ Papadimitriou & Yannakakis (1991) prove MaxSNPcompleteness.
 ^ Håstad (2001)
 ^ Trevisan et al. (2000)
 ^ Khot et al. (2007).
 ^ Newman (2008).
References
 Ausiello, Giorgio; Crescenzi, Pierluigi; Gambosi, Giorgio; Kann, Viggo; MarchettiSpaccamela, Alberto; Protasi, Marco (2003), Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, Springer.

 Maximum cut (optimisation version) is the problem ND14 in Appendix B (page 399).
 Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NPCompleteness, W.H. Freeman, ISBN 0716710455.

 Maximum cut (decision version) is the problem ND16 in Appendix A2.2.
 Maximum bipartite subgraph (decision version) is the problem GT25 in Appendix A1.2.
 Gaur, Daya Ram; Krishnamurti, Ramesh (2007), "LP rounding and extensions", in Gonzalez, Teofilo F., Handbook of Approximation Algorithms and Metaheuristics, Chapman & Hall/CRC.
 Goemans, Michel X.; Williamson, David P. (1995), "Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming", Journal of the ACM 42 (6): 1115–1145, doi:10.1145/227683.227684.
 Hadlock, F. (1975), "Finding a Maximum Cut of a Planar Graph in Polynomial Time", SIAM J. Comput. 4 (3): 221–225, doi:10.1137/0204019.
 Håstad, Johan (2001), "Some optimal inapproximability results", Journal of the ACM 48 (4): 798–859, doi:10.1145/502090.502098.
 Karp, Richard M. (1972), "Reducibility among combinatorial problems", in Miller, R. E.; Thacher, J. W., Complexity of Computer Computation, Plenum Press, pp. 85–103.
 Khot, Subhash; Kindler, Guy; Mossel, Elchanan; O'Donnell, Ryan (2007), "Optimal inapproximability results for MAXCUT and other 2variable CSPs?", SIAM Journal on Computing 37 (1): 319–357, doi:10.1137/S0097539705447372.
 Khuller, Samir; Raghavachari, Balaji; Young, Neal E. (2007), "Greedy methods", in Gonzalez, Teofilo F., Handbook of Approximation Algorithms and Metaheuristics, Chapman & Hall/CRC.
 Mitzenmacher, Michael; Upfal, Eli (2005), Probability and Computing: Randomized Algorithms and Probabilistic Analysis, Cambridge.
 Motwani, Rajeev; Raghavan, Prabhakar (1995), Randomized Algorithms, Cambridge.
 Newman, Alantha (2008), "Max cut", in Kao, MingYang, Encyclopedia of Algorithms, Springer, pp. 1, doi:10.1007/9780387301624_219.
 Papadimitriou, Christos H.; Yannakakis, Mihalis (1991), "Optimization, approximation, and complexity classes", Journal of Computer and System Sciences 43 (3): 425–440, doi:10.1016/00220000(91)90023X.
 Trevisan, Luca; Sorkin, Gregory; Sudan, Madhu; Williamson, David (2000), "Gadgets, Approximation, and Linear Programming", Proceedings of the 37th IEEE Symposium on Foundations of Computer Science: 617–626.
Further reading
 Barahona, Francisco; Grötschel, Martin; Jünger, Michael; Reinelt, Gerhard (1988), "An application of combinatorial optimization to statistical physics and circuit layout design", Operations Research 36 (3): 493–513, doi:10.1287/opre.36.3.493, JSTOR 170992.
External links
 Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, Gerhard Woeginger (2000), "Maximum Cut", in "A compendium of NP optimization problems".
Categories: Graph theory objects
 Combinatorial optimization
 NPcomplete problems
 Computational problems in graph theory
Wikimedia Foundation. 2010.