 Cut (graph theory)

In graph theory, a cut is a partition of the vertices of a graph into two disjoint subsets. The cutset of the cut is the set of edges whose end points are in different subsets of the partition. Edges are said to be crossing the cut if they are in its cutset.
In an unweighted undirected graph, the size or weight of a cut is the number of edges crossing the cut. In a weighted graph, the same term is defined by the sum of the weights of the edges crossing the cut.
In a flow network, an st cut is a cut that requires the source and the sink to be in different subsets, and its cutset only consists of edges going from the source's side to the sink's side. The capacity of an st cut is defined by the sum of capacity of each edge in the cutset.
The cut of a graph can sometimes refer to its cutset instead of the partition.
Contents
Definition
 A cut C = (S,T) is a partition V of a graph G = (V,E).
 An st cut C = (S,T) of a network N = (V,E) is a cut of N such that and , where s and t are the source and the sink of N respectively.
 The cutset of a cut C = (S,T) is the set .
 The size of a cut C = (S,T) is the number of edges in the cutset. If the edges are weighted, the value of the cut is the sum of the weights.
Minimum cut
Main article: Minimum cutA cut is minimum if the size of the cut is not larger than the size of any other cut. The illustration on the right shows a minimum cut: the size of this cut is 2, and there is no cut of size 1 because the graph is bridgeless.
The maxflow mincut theorem proves that the maximum network flow and the sum of the cutedge weights of any minimum cut that separates the source and the sink are equal. There are polynomialtime methods to solve the mincut problem, notably the EdmondsKarp algorithm.
Maximum cut
Main article: Maximum cutA 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 maxcut problem is one of Karp's 21 NPcomplete problems. The max cut problem is also APXhard, meaning that there is no polynomialtime approximation scheme for it unless P = NP.
Note that mincut and maxcut 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 maxflow problem is the dual of the mincut problem.
Sparsest cut
The Sparsest cut problem is to bipartition the vertices so as to minimize the ratio of the number of edges across the cut divided by the number of vertices in the smaller half of the partition. This objective function favors solutions that are both sparse (few edges crossing the cut) and balanced (close to a bisection). The problem is known to be NPHard, and the best known algorithm is an approximation due to Arora, Rao & Vazirani (2009).
See also
References
 Arora, Sanjeev; Rao, Satish; Vazirani, Umesh (2009), "Expander flows, geometric embeddings and graph partitioning", J. ACM (ACM) 56 (2): 1–37, doi:10.1145/1502793.1502794, ISSN 00045411
 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (2001). Introduction to Algorithms, Second Edition. MIT Press and McGrawHill. pp. 563,655,1043. ISBN 0262032937.
 Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NPCompleteness. W.H. Freeman. ISBN 0716710455. A2.2: ND16, pg.210.
 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), 11151145
 R. M. Karp, Reducibility among combinatorial problems, in R. E. Miller and J. W. Thacher (eds.), Complexity of Computer Computation, Plenum Press, New York, 85103 (1972)
 S. Khot, G. Kindler, E. Mossel, and R. O’Donnell, Optimal inapproximability results for MAXCUT and other twovariable CSPs?, In Proceedings of the 45th IEEE Symposium on Foundations of Computer Science, pp. 146–154, 2004.
 Vijay V. Vazirani (2004). Approximation Algorithms. Springer. pp. 97–98. ISBN 3540653678.
 Meira, Luis A. A.. "Semideﬁnite Programming Based Algorithms for the Sparsest Cut Problem". http://www.ic.unicamp.br/~fkm/publication/Rairo11.pdf. Retrieved 6 September 2011.
Categories: Graph connectivity
 Combinatorial optimization
Wikimedia Foundation. 2010.
Look at other dictionaries:
Graph theory — In mathematics and computer science, graph theory is the study of graphs : mathematical structures used to model pairwise relations between objects from a certain collection. A graph in this context refers to a collection of vertices or nodes and … Wikipedia
Connectivity (graph theory) — In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements (nodes or edges) which need to be removed to disconnect the remaining nodes from each other[1]. It is… … Wikipedia
Minor (graph theory) — In graph theory, an undirected graph H is called a minor of the graph G if H is isomorphic to a graph that can be obtained by zero or more edge contractions on a subgraph of G. The theory of graph minors began with Wagner s theorem that a graph… … Wikipedia
Bridge (graph theory) — A graph with 6 bridges (highlighted in red) An undirected connected graph with no cut … Wikipedia
Vertex (graph theory) — For other uses, see Vertex (disambiguation). A graph with 6 vertices and 7 edges where the vertex number 6 on the far left is a leaf vertex or a pendant vertex In graph theory, a vertex (plural vertices) or node is the fundamental unit out of… … Wikipedia
Glossary of graph theory — Graph theory is a growing area in mathematical research, and has a large specialized vocabulary. Some authors use the same word with different meanings. Some authors use different words to mean the same thing. This page attempts to keep up with… … Wikipedia
List of graph theory topics — This is a list of graph theory topics, by Wikipedia page. See glossary of graph theory for basic terminology Contents 1 Examples and types of graphs 2 Graph coloring 3 Paths and cycles 4 … Wikipedia
König's theorem (graph theory) — In the mathematical area of graph theory, König s theorem describes an equivalence between the maximum matching problem and the minimum vertex cover problem in bipartite graphs. Setting A graph is bipartite if its vertices can be partitioned into … Wikipedia
Transportation network (graph theory) — A transportation network is a type of directed, weighted graph or network.Transportation networks are used to model the flow of commodity, information, or traffic (see transport network). Definitions A transportation network G is a graph with… … Wikipedia
Cut — may refer to: The act of cutting, the separation of an object into two through acutely directed force Contents 1 Mathematics 2 Computing 3 … Wikipedia