Cut (graph theory)
From Wikipedia, the free encyclopedia
In graph theory, a cut is a partition of the vertices of a graph into two sets. More formally, let G(V, E) denote a graph. A cut is a partition of the vertices V into two sets S and T. Any edge (u,v) ∈ E with u ∈ S and v ∈ T (or u ∈ T and v ∈ S, in case of a directed graph) is said to be crossing the cut and is a cut edge.
The size of a cut is the total number of edges crossing the cut. In weighted graphs, the size of the cut is defined to be sum of weights of the edges crossing the cut.
[edit] Minimal and maximal cuts
A cut is minimal if the size of the cut is not larger than the size of any other cut. The max-flow min-cut theorem proves that the maximal network flow and the sum of the cut-edge weights of any minimal cut that separates the source and the sink are equal. There are polynomial-time algorithms to solve the min-cut problem, though more than one min-cut can exist.
A cut is maximal if the size of the cut is not smaller than the size of any other cut. Max-cut problem is one of Karp's 21 NP-complete problems. Consequently no polynomial-time algorithms for max-cut can be expected. Proof of NP-completeness is by transformation from maximum 2-satisfiability (a restriction of the maximum satisfiability problem).
A polynomial-time algorithm to find maximum cuts in planar graphs exists. There is a simple 0.5-randomized approximation algorithm, which is also the best purely combinatorial algorithm for maximal cuts. The best known max-cut algorithm is an 0.878-approximation algorithm by Goemans and Williamson using semidefinite programming and randomized rounding. This algorithm yields (essentially) the best possible approximation ratio for the problem.
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.
[edit] See also
[edit] References
- R. M. Karp, Reducibility among combinatorial problems, in R. E. Miller and J. W. Thacher (eds.), Complexity of Computer Computation, Plenum Press, New York, 85-103 (1972)
- M. X. Goemans, and D. P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM, 42, 6 (Nov. 1995), 1115-1145
- S. Khot, G. Kindler, E. Mossel, and R. O’Donnell, Optimal inapproximability results for MAX-CUT and other two-variable CSPs?, In Proceedings of the 45th IEEE Symposium on Foundations of Computer Science, pp. 146–154, 2004.
- Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5. A2.2: ND16, pg.210.
