CUT (GRAPH THEORY)

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. In network flow, the size of a cut is defined to be the sum of weights of the edges crossing the cut from the source side to the sink side (but not the ones that go the other way).

Contents

Minimal and maximal cuts

See also

References

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 methods to solve the min-cut problem, notably the Ford-Fulkerson algorithm.
A cut is ''maximal'' if the size of the cut is not smaller than the size of any other cut. The max-cut problem is one of Karp's 21 NP-complete problems. Consequently no polynomial-time algorithms for max-cut can be expected, however, various meta-heuristic search methods can efficiently produce approximate solutions. The proof of max-cut problem's NP-completeness comes 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.

See also

★ Prim's algorithm

★ Edmonds-Karp Algorithm

★ Graph cuts in computer vision

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, , , W.H. Freeman, 1979, ISBN 0-7167-1045-5 A2.2: ND16, pg.210.