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) \in E with u \in S and v \in T (or u \in T and v \in 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).

[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 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; the proof comes by transformation from maximum 2-satisfiability (a restriction of the maximum satisfiability problem). Consequently no polynomial-time algorithms for max-cut can be expected. However, a polynomial-time algorithm to find maximum cuts in planar graphs exists. Also various meta-heuristic search methods can sometimes efficiently produce approximate solutions. There is a simple 0.5-randomized approximation algorithm: for each vertex flip a coin to decide to which half of the partition to assign it. The best known max-cut algorithm is the famous 0.878…-approximation algorithm by Goemans and Williamson using semidefinite programming and randomized rounding.

The max cut problem is APX-hard, meaning that there is no polynomial-time approximation scheme (PTAS) for it unless P = NP. Moreover, Hastad has shown that it is NP-hard to approximate the max cut value to better than 16 / 17 = 0.941…. Assuming the Unique Games Conjecture (UGC), it is in fact NP-hard to approximate the max cut value by a factor of αGW + ε for any ε > 0, where αGW = 0.878… is the approximation factor of Goemans-Williamson. (In other words, assuming the UGC and that BPP \neq NP, the Goemans-Williamson algorithm yields essentially the best polynomial-time-computable 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