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 Max-Cut 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 Max-Cut. 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 Max-Cut problem is often, but not always, restricted to non-negative weights, because negative weights can change the nature of the problem.

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 NP-complete. It is easy to see that the problem is in NP: a yes answer is easy to prove by presenting a large enough cut. The NP-completeness of the problem can be shown, for example, by a transformation from maximum 2-satisfiability (a restriction of the maximum satisfiability problem).^[1] The weighted version of the decision problem was one of Karp's 21 NP-complete problems;^[2] Karp showed the NP-completeness 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 Max-Cut and is defined as:

Given a graph G, find a maximum cut.

Polynomial-time algorithms

As the Max-Cut Problem is NP-hard, no polynomial-time algorithms for Max-Cut in general graphs are known.

However, in planar graphs, the Maximum-Cut Problem is dual to the route inspection problem (the problem of finding a shortest tour that visits each edge of a graph at least once), in the sense that the edges that do not belong to a maximum cut-set of a graph G are the duals of the edges that are doubled in an optimal inspection tour of the dual graph of G. The optimal inspection tour forms a self-intersecting curve that separates the plane into two subsets, the subset of points for which the winding number of the curve is even and the subset for which the winding number is odd; these two subsets form a cut that includes all of the edges whose duals appear an odd number of times in the tour. The route inspection problem may be solved in polynomial time, and this duality allows the maximum cut problem to also be solved in polynomial time for planar graphs.^[3] The Maximum-Bisection problem is known however to be NP-hard.^[4]

Approximation algorithms

The Max-Cut Problem is APX-hard,^[5] meaning that there is no polynomial-time approximation scheme (PTAS), arbitrarily close to the optimal solution, for it, unless P = NP. Thus, every polynomial-time approximation algorithm achieves an approximation ratio strictly less than one.

There is a simple randomized 0.5-approximation algorithm: for each vertex flip a coin to decide to which half of the partition to assign it.^[6]^[7] 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 polynomial-time 0.5-approximation algorithm as well.^[8]^[9] One such algorithm starts with an arbitrary partition of the vertices of the given graph $G=(V,E)$ and repeatedly moves one vertex at a time from one side of the partition to the other, improving the solution at each step, until no more improvements of this type can be made. The number of iterations is at most $|E|$ because the algorithm improves the cut by at least one edge at each step. When the algorithm terminates, at least half of the edges incident to every vertex belong to the cut, for otherwise moving the vertex would improve the cut. Therefore, the cut includes at least $|E|/2$ edges.

The polynomial-time approximation algorithm for Max-Cut with the best known approximation ratio is a method by Goemans and Williamson using semidefinite programming and randomized rounding that achieves an approximation ratio $\alpha \approx 0.878$ , where $\alpha ={\tfrac {2}{\pi }}\min _{0\leq \theta \leq \pi }{\tfrac {\theta }{1-\cos \theta }}$ .^[10]^[11] If the unique games conjecture is true, this is the best possible approximation ratio for maximum cut.^[12] Without such unproven assumptions, it has been proven to be NP-hard to approximate the max-cut value with an approximation ratio better than ${\tfrac {16}{17}}\approx 0.941$ .^[13]^[14]

Notes

References

Ausiello, Giorgio; Crescenzi, Pierluigi; Gambosi, Giorgio; Kann, Viggo; Marchetti-Spaccamela, 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 NP-Completeness, W.H. Freeman, ISBN 0-7167-1045-5 .

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 .
Jansen, Klaus; Karpinski, Marek; Lingas, Andrzej; Seidel, Eike (2005), "Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs", SIAM Journal on Computing, 35 (1), doi:10.1137/s009753970139567x .
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 MAX-CUT and other 2-variable 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, Ming-Yang, Encyclopedia of Algorithms, Springer, p. 1, doi:10.1007/978-0-387-30162-4_219, ISBN 978-0-387-30770-1 .
Papadimitriou, Christos H.; Yannakakis, Mihalis (1991), "Optimization, approximation, and complexity classes", Journal of Computer and System Sciences, 43 (3): 425–440, doi:10.1016/0022-0000(91)90023-X .
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 .

External links

Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, Gerhard Woeginger (2000), "Maximum Cut", in "A compendium of NP optimization problems".
Andrea Casini, Nicola Rebagliati (2012), "A Python library for solving Max Cut"

This article is issued from Wikipedia - version of the 8/15/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.