Maximum Graph Cut
Jump to navigation
Jump to search
A Maximum Graph Cut is a Bipartite Graph that ...
- AKA: Cut (Graph Theory), Maximum Cut.
- See: Bipartite Graph, Cycle Graph#Terminology, Karp's 21 NP-Complete Problems, Constant-Factor Approximation Algorithm, Approximation Ratio, Semidefinite Programming, Linear Programming#Duality, Linear Programming, Objective Function, Computers And Intractability: A Guide to The Theory of NP-Completeness, Journal of The ACM.
References
2014
- (Wikipedia, 2014) ⇒ http://en.wikipedia.org/wiki/cut_(graph_theory)#Maximum_cut Retrieved:2014-5-4.
- A cut is maximum if the size of the cut is not smaller than the size of any other cut. The illustration on the right shows a maximum cut: the size of the cut is equal to 5, and there is no cut of size |E| because the graph is not bipartite (there is an odd cycle).
In general, finding a maximum cut is computationally hard. The max-cut problem is one of Karp's 21 NP-complete problems. The max-cut problem is also APX-hard, meaning that there is no polynomial-time approximation scheme for it unless P = NP. However, it can be approximated to within a constant approximation ratio using semidefinite programming. Note that min-cut and max-cut are not dual problems in the linear programming sense, even though one gets from one problem to other by changing min to max in the objective function. The max-flow problem is the dual of the min-cut problem.
- A cut is maximum if the size of the cut is not smaller than the size of any other cut. The illustration on the right shows a maximum cut: the size of the cut is equal to 5, and there is no cut of size |E| because the graph is not bipartite (there is an odd cycle).