Cut (graph theory)

Last updated August 30, 2024

In graph theory, a cut is a partition of the vertices of a graph into two disjoint subsets.^[1] Any cut determines a cut-set, the set of edges that have one endpoint in each subset of the partition. These edges are said to cross the cut. In a connected graph, each cut-set determines a unique cut, and in some cases cuts are identified with their cut-sets rather than with their vertex partitions.

In a flow network, an s–t cut is a cut that requires the source and the sink to be in different subsets, and its cut-set only consists of edges going from the source's side to the sink's side. The capacity of an s–t cut is defined as the sum of the capacity of each edge in the cut-set.

Definition

A cut $C = (S, T)$ is a partition of $V$ of a graph $G = (V, E)$ into two subsets $S$ and $T$ . The cut-set of a cut $C = (S, T)$ is the set ${(u, v) \in E | u \in S, v \in T}$ of edges that have one endpoint in $S$ and the other endpoint in $T$ . If $s$ and $t$ are specified vertices of the graph $G$ , then an $s$ – $t$ cut is a cut in which $s$ belongs to the set $S$ and $t$ belongs to the set $T$ .

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 value or weight is defined by the sum of the weights of the edges crossing the cut.

A bond is a cut-set that does not have any other cut-set as a proper subset.

Minimum cut

A cut is minimum if the size or weight 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 max-flow min-cut theorem proves that the maximum network flow and the sum of the cut-edge weights of any minimum cut that separates the source and the sink are equal. There are polynomial-time methods to solve the min-cut problem, notably the Edmonds–Karp algorithm.^[2]

Maximum cut

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 6, or |E| (the number of edges), because the graph is not bipartite (there is an odd cycle).

In general, finding a maximum cut is computationally hard.^[3] The max-cut problem is one of Karp's 21 NP-complete problems.^[4] The max-cut problem is also APX-hard, meaning that there is no polynomial-time approximation scheme for it unless P = NP.^[5] However, it can be approximated to within a constant approximation ratio using semidefinite programming.^[6]

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.^[7]

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 NP-hard, and the best known approximation algorithm is an $O({\sqrt {\log n}})$ approximation due to Arora, Rao & Vazirani (2009).^[8]

Cut space

The family of all cut sets of an undirected graph is known as the cut space of the graph. It forms a vector space over the two-element finite field of arithmetic modulo two, with the symmetric difference of two cut sets as the vector addition operation, and is the orthogonal complement of the cycle space.^[9]^[10] If the edges of the graph are given positive weights, the minimum weight basis of the cut space can be described by a tree on the same vertex set as the graph, called the Gomory–Hu tree.^[11] Each edge of this tree is associated with a bond in the original graph, and the minimum cut between two nodes s and t is the minimum weight bond among the ones associated with the path from s to t in the tree.

Related Research Articles

In computer science and optimization theory, the max-flow min-cut theorem states that in a flow network, the maximum amount of flow passing from the source to the sink is equal to the total weight of the edges in a minimum cut, i.e., the smallest total weight of the edges which if removed would disconnect the source from the sink.

In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint and independent sets $and, that is, every edge connects a vertex in to one in . Vertex sets and are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.$

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

In graph theory, an independent set, stable set, coclique or anticlique is a set of vertices in a graph, no two of which are adjacent. That is, it is a set $of vertices such that for every two vertices in, there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in . A set is independent if and only if it is a clique in the graph's complement. The size of an independent set is the number of vertices it contains. Independent sets have also been called "internally stable sets", of which "stable set" is a shortening.$

In graph theory, a vertex cover of a graph is a set of vertices that includes at least one endpoint of every edge of the graph.

In the mathematical discipline of graph theory, a matching or independent edge set in an undirected graph is a set of edges without common vertices. In other words, a subset of the edges is a matching if each vertex appears in at most one edge of that matching. Finding a matching in a bipartite graph can be treated as a network flow problem.

<span class="mw-page-title-main">Dominating set</span> Subset of a graphs nodes such that all other nodes link to at least one

In graph theory, a dominating set for a graph $G$ is a subset $D$ of its vertices, such that any vertex of $G$ is in $D$ , or has a neighbor in $D$ . The domination number $γ(G)$ is the number of vertices in a smallest dominating set for $G$ .

In graph theory and graph algorithms, a feedback arc set or feedback edge set in a directed graph is a subset of the edges of the graph that contains at least one edge out of every cycle in the graph. Removing these edges from the graph breaks all of the cycles, producing an acyclic subgraph of the given graph, often called a directed acyclic graph. A feedback arc set with the fewest possible edges is a minimum feedback arc set and its removal leaves a maximum acyclic subgraph; weighted versions of these optimization problems are also used. If a feedback arc set is minimal, meaning that removing any edge from it produces a subset that is not a feedback arc set, then it has an additional property: reversing all of its edges, rather than removing them, produces a directed acyclic graph.

Set packing is a classical NP-complete problem in computational complexity theory and combinatorics, and was one of Karp's 21 NP-complete problems. Suppose one has a finite set S and a list of subsets of S. Then, the set packing problem asks if some k subsets in the list are pairwise disjoint.

In graph theory, a minimum cut or min-cut of a graph is a cut that is minimal in some metric.

<span class="mw-page-title-main">Kőnig's theorem (graph theory)</span> Theorem showing that maximum matching and minimum vertex cover are equivalent for bipartite graphs

In the mathematical area of graph theory, Kőnig's theorem, proved by Dénes Kőnig, describes an equivalence between the maximum matching problem and the minimum vertex cover problem in bipartite graphs. It was discovered independently, also in 1931, by Jenő Egerváry in the more general case of weighted graphs.

In computer science, the Hopcroft–Karp algorithm is an algorithm that takes a bipartite graph as input and produces a maximum-cardinality matching as output — a set of as many edges as possible with the property that no two edges share an endpoint. It runs in $time in the worst case, where is set of edges in the graph, is set of vertices of the graph, and it is assumed that . In the case of dense graphs the time bound becomes, and for sparse random graphs it runs in time with high probability.$

Maximum cardinality matching is a fundamental problem in graph theory. We are given a graph $G$ , and the goal is to find a matching containing as many edges as possible; that is, a maximum cardinality subset of the edges such that each vertex is adjacent to at most one edge of the subset. As each edge will cover exactly two vertices, this problem is equivalent to the task of finding a matching that covers as many vertices as possible.

In mathematics, a graph partition is the reduction of a graph to a smaller graph by partitioning its set of nodes into mutually exclusive groups. Edges of the original graph that cross between the groups will produce edges in the partitioned graph. If the number of resulting edges is small compared to the original graph, then the partitioned graph may be better suited for analysis and problem-solving than the original. Finding a partition that simplifies graph analysis is a hard problem, but one that has applications to scientific computing, VLSI circuit design, and task scheduling in multiprocessor computers, among others. Recently, the graph partition problem has gained importance due to its application for clustering and detection of cliques in social, pathological and biological networks. For a survey on recent trends in computational methods and applications see Buluc et al. (2013). Two common examples of graph partitioning are minimum cut and maximum cut problems.

In graph theory, a clique cover or partition into cliques of a given undirected graph is a collection of cliques that cover the whole graph. A minimum clique cover is a clique cover that uses as few cliques as possible. The minimum $k$ for which a clique cover exists is called the clique cover number of the given graph.

<span class="mw-page-title-main">Maximum cut</span> Problem of finding a maximum cut in a graph

In a graph, a maximum cut is a cut whose size is at least the size of any other cut. That is, it is a partition of the graph's vertices into two complementary sets $S$ and $T$ , such that the number of edges between $S$ and $T$ is as large as possible. Finding such a cut is known as the max-cut problem.

In mathematics, the minimum $k$ -cut is a combinatorial optimization problem that requires finding a set of edges whose removal would partition the graph to at least $k$ connected components. These edges are referred to as $k$ -cut. The goal is to find the minimum-weight $k$ -cut. This partitioning can have applications in VLSI design, data-mining, finite elements and communication in parallel computing.

Approximate max-flow min-cut theorems are mathematical propositions in network flow theory. Approximate max-flow min-cut theorems deal with the relationship between maximum flow rate ("max-flow") and minimum cut ("min-cut") in a multi-commodity flow problem. The theorems have enabled the development of approximation algorithms for use in graph partition and related problems.

In combinatorial optimization, the matroid parity problem is a problem of finding the largest independent set of paired elements in a matroid. The problem was formulated by Lawler (1976) as a common generalization of graph matching and matroid intersection. It is also known as polymatroid matching, or the matchoid problem.

In graph theory, the cutwidth of an undirected graph is the smallest integer $with the following property: there is an ordering of the vertices of the graph, such that every cut obtained by partitioning the vertices into earlier and later subsets of the ordering is crossed by at most edges. That is, if the vertices are numbered, then for every, the number of edges with and is at most .$

References

↑ "NetworkX 2.6.2 documentation". networkx.algorithms.cuts.cut_size. Archived from the original on 2021-11-18. Retrieved 2021-12-10. A cut is a partition of the nodes of a graph into two sets. The cut size is the sum of the weights of the edges "between" the two sets of nodes.
↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), Introduction to Algorithms (2nd ed.), MIT Press and McGraw-Hill, p. 563,655,1043, ISBN 0-262-03293-7 .
↑ Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness , W.H. Freeman, A2.2: ND16, p. 210, ISBN 0-7167-1045-5 .
↑ Karp, R. M. (1972), "Reducibility among combinatorial problems", in Miller, R. E.; Thacher, J. W. (eds.), Complexity of Computer Computation, New York: Plenum Press, pp. 85–103.
↑ Khot, S.; Kindler, G.; Mossel, E.; O’Donnell, R. (2004), "Optimal inapproximability results for MAX-CUT and other two-variable CSPs?" (PDF), Proceedings of the 45th IEEE Symposium on Foundations of Computer Science, pp. 146–154, archived (PDF) from the original on 2019-07-15, retrieved 2019-08-29.
↑ Goemans, M. X.; Williamson, D. P. (1995), "Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming", Journal of the ACM , 42 (6): 1115–1145, doi: 10.1145/227683.227684 .
↑ Vazirani, Vijay V. (2004), Approximation Algorithms, Springer, pp. 97–98, ISBN 3-540-65367-8 .
↑ Arora, Sanjeev; Rao, Satish; Vazirani, Umesh (2009), "Expander flows, geometric embeddings and graph partitioning", J. ACM, 56 (2), ACM: 1–37, doi:10.1145/1502793.1502794, S2CID 263871111 .
↑ Gross, Jonathan L.; Yellen, Jay (2005), "4.6 Graphs and Vector Spaces", Graph Theory and Its Applications (2nd ed.), CRC Press, pp. 197–207, ISBN 9781584885054 .
↑ Diestel, Reinhard (2012), "1.9 Some linear algebra", Graph Theory, Graduate Texts in Mathematics, vol. 173, Springer, pp. 23–28.
↑ Korte, B. H.; Vygen, Jens (2008), "8.6 Gomory–Hu Trees", Combinatorial Optimization: Theory and Algorithms, Algorithms and Combinatorics, vol. 21, Springer, pp. 180–186, ISBN 978-3-540-71844-4 .

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[networkx.algorithms.cuts.cut_size-1] "NetworkX 2.6.2 documentation". networkx.algorithms.cuts.cut_size. Archived from the original on 2021-11-18. Retrieved 2021-12-10. A cut is a partition of the nodes of a graph into two sets. The cut size is the sum of the weights of the edges "between" the two sets of nodes.

[2] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), Introduction to Algorithms (2nd ed.), MIT Press and McGraw-Hill, p. 563,655,1043, ISBN 0-262-03293-7 .

[3] Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness , W.H. Freeman, A2.2: ND16, p. 210, ISBN 0-7167-1045-5 .

[4] Karp, R. M. (1972), "Reducibility among combinatorial problems", in Miller, R. E.; Thacher, J. W. (eds.), Complexity of Computer Computation, New York: Plenum Press, pp. 85–103.

[5] Khot, S.; Kindler, G.; Mossel, E.; O’Donnell, R. (2004), "Optimal inapproximability results for MAX-CUT and other two-variable CSPs?" (PDF), Proceedings of the 45th IEEE Symposium on Foundations of Computer Science, pp. 146–154, archived (PDF) from the original on 2019-07-15, retrieved 2019-08-29.

[6] Goemans, M. X.; Williamson, D. P. (1995), "Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming", Journal of the ACM , 42 (6): 1115–1145, doi: 10.1145/227683.227684 .

[7] Vazirani, Vijay V. (2004), Approximation Algorithms, Springer, pp. 97–98, ISBN 3-540-65367-8 .

[8] Arora, Sanjeev; Rao, Satish; Vazirani, Umesh (2009), "Expander flows, geometric embeddings and graph partitioning", J. ACM, 56 (2), ACM: 1–37, doi:10.1145/1502793.1502794, S2CID 263871111 .

[gy-9] Gross, Jonathan L.; Yellen, Jay (2005), "4.6 Graphs and Vector Spaces", Graph Theory and Its Applications (2nd ed.), CRC Press, pp. 197–207, ISBN 9781584885054 .

[diestel-10] Diestel, Reinhard (2012), "1.9 Some linear algebra", Graph Theory, Graduate Texts in Mathematics, vol. 173, Springer, pp. 23–28.

[11] Korte, B. H.; Vygen, Jens (2008), "8.6 Gomory–Hu Trees", Combinatorial Optimization: Theory and Algorithms, Algorithms and Combinatorics, vol. 21, Springer, pp. 180–186, ISBN 978-3-540-71844-4 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]