341:
291:
431:
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
600:
675:
308:
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
358:
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 |
592:
469:
378:
612:
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.
927:
66:, each cut-set determines a unique cut, and in some cases cuts are identified with their cut-sets rather than with their vertex partitions.
953:
881:
812:
688:
650:
374:
738:
553:
769:(1995), "Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming",
264:
47:
948:
548:
329:
641:
324:
and the sum of the cut-edge weights of any minimum cut that separates the source and the sink are equal. There are
523:. Each edge of this tree is associated with a bond in the original graph, and the minimum cut between two nodes
390:
317:
84:
78:
512:
435:
568:
504:
310:
43:
628:
558:
500:
766:
516:
386:
382:
58:, the set of edges that have one endpoint in each subset of the partition. These edges are said to
520:
852:
771:
496:
408:
404:
400:
39:
923:
877:
871:
808:
707:(1972), "Reducibility among combinatorial problems", in Miller, R. E.; Thacher, J. W. (eds.),
684:
646:
898:
680:
844:
780:
670:
666:
632:
624:
563:
363:
325:
63:
373:
In general, finding a maximum cut is computationally hard. The max-cut problem is one of
915:
832:
800:
762:
636:
942:
856:
828:
727:
51:
407:
sense, even though one gets from one problem to other by changing min to max in the
723:
704:
492:
488:
321:
70:
31:
432:
problem is known to be NP-hard, and the best known approximation algorithm is an
508:
349:
299:
381:, meaning that there is no polynomial-time approximation scheme for it unless
848:
728:"Optimal inapproximability results for MAX-CUT and other two-variable CSPs?"
367:
93:
only consists of edges going from the source's side to the sink's side. The
511:. If the edges of the graph are given positive weights, the minimum weight
922:, Algorithms and Combinatorics, vol. 21, Springer, pp. 180–186,
785:
735:
Proceedings of the 45th IEEE Symposium on
Foundations of Computer Science
573:
903:, Graduate Texts in Mathematics, vol. 173, Springer, pp. 23–28
870:
Gross, Jonathan L.; Yellen, Jay (2005), "4.6 Graphs and Vector Spaces",
531:
is the minimum weight bond among the ones associated with the path from
97:
of an s–t cut is defined as the sum of the capacity of each edge in the
835:(2009), "Expander flows, geometric embeddings and graph partitioning",
17:
676:
Computers and
Intractability: A Guide to the Theory of NP-Completeness
282:
is a cut-set that does not have any other cut-set as a proper subset.
275:
is defined by the sum of the weights of the edges crossing the cut.
340:
290:
483:
The family of all cut sets of an undirected graph is known as the
339:
289:
645:(2nd ed.), MIT Press and McGraw-Hill, p. 563,655,1043,
503:
of two cut sets as the vector addition operation, and is the
385:. However, it can be approximated to within a constant
263:
of a cut is the number of edges crossing the cut. In a
897:
Diestel, Reinhard (2012), "1.9 Some linear algebra",
438:
27:
Partition of a graph's nodes into 2 disjoint subsets
463:
362:| (the number of edges), because the graph is not
328:methods to solve the min-cut problem, notably the
920:Combinatorial Optimization: Theory and Algorithms
726:; Kindler, G.; Mossel, E.; O’Donnell, R. (2004),
519:on the same vertex set as the graph, called the
472:
918:; Vygen, Jens (2008), "8.6 Gomory–Hu Trees",
876:(2nd ed.), CRC Press, pp. 197–207,
8:
784:
711:, New York: Plenum Press, pp. 85–103
445:
437:
584:
515:of the cut space can be described by a
255:In an unweighted undirected graph, the
7:
221:are specified vertices of the graph
89:to be in different subsets, and its
464:{\displaystyle O({\sqrt {\log n}})}
205:of edges that have one endpoint in
709:Complexity of Computer Computation
396:Note that min-cut and max-cut are
25:
873:Graph Theory and Its Applications
597:networkx.algorithms.cuts.cut_size
473:Arora, Rao & Vazirani (2009)
744:from the original on 2019-07-15
603:from the original on 2021-11-18
593:"NetworkX 2.6.2 documentation"
458:
442:
377:. The max-cut problem is also
375:Karp's 21 NP-complete problems
1:
554:Graph cuts in computer vision
807:, Springer, pp. 97–98,
549:Connectivity (graph theory)
415:problem is the dual of the
77:is a cut that requires the
970:
954:Combinatorial optimization
642:Introduction to Algorithms
347:
297:
209:and the other endpoint in
487:of the graph. It forms a
805:Approximation Algorithms
391:semidefinite programming
320:proves that the maximum
318:max-flow min-cut theorem
849:10.1145/1502793.1502794
681:A2.2: ND16, p. 210
54:. Any cut determines a
465:
345:
330:Edmonds–Karp algorithm
295:
786:10.1145/227683.227684
629:Leiserson, Charles E.
569:Bridge (graph theory)
505:orthogonal complement
491:over the two-element
471:approximation due to
466:
343:
293:
737:, pp. 146–154,
559:Split (graph theory)
501:symmetric difference
436:
429:sparsest cut problem
387:approximation ratio
248:belongs to the set
240:belongs to the set
949:Graph connectivity
801:Vazirani, Vijay V.
772:Journal of the ACM
461:
409:objective function
405:linear programming
346:
296:
236:is a cut in which
127:is a partition of
929:978-3-540-71844-4
767:Williamson, D. P.
671:Johnson, David S.
667:Garey, Michael R.
633:Rivest, Ronald L.
625:Cormen, Thomas H.
456:
146:into two subsets
16:(Redirected from
961:
934:
932:
912:
906:
904:
894:
888:
886:
867:
861:
859:
843:(2), ACM: 1–37,
825:
819:
817:
797:
791:
789:
788:
779:(6): 1115–1145,
759:
753:
751:
750:
749:
743:
732:
720:
714:
712:
701:
695:
693:
679:, W.H. Freeman,
663:
657:
655:
621:
615:
614:
609:
608:
589:
564:Vertex separator
470:
468:
467:
462:
457:
446:
418:
414:
403:problems in the
383:P = NP
251:
247:
243:
239:
233:
229:
224:
220:
216:
212:
208:
204:
172:
153:
149:
145:
130:
126:
52:disjoint subsets
21:
969:
968:
964:
963:
962:
960:
959:
958:
939:
938:
937:
930:
914:
913:
909:
896:
895:
891:
884:
869:
868:
864:
833:Vazirani, Umesh
831:; Rao, Satish;
827:
826:
822:
815:
799:
798:
794:
761:
760:
756:
747:
745:
741:
730:
722:
721:
717:
703:
702:
698:
691:
665:
664:
660:
653:
637:Stein, Clifford
623:
622:
618:
606:
604:
591:
590:
586:
582:
545:
481:
434:
433:
425:
416:
412:
352:
338:
326:polynomial-time
302:
288:
249:
245:
241:
237:
231:
227:
222:
218:
214:
210:
206:
174:
159:
151:
147:
132:
128:
113:
107:
64:connected graph
28:
23:
22:
15:
12:
11:
5:
967:
965:
957:
956:
951:
941:
940:
936:
935:
928:
907:
889:
882:
862:
829:Arora, Sanjeev
820:
813:
792:
763:Goemans, M. X.
754:
715:
696:
689:
658:
651:
616:
583:
581:
578:
577:
576:
571:
566:
561:
556:
551:
544:
541:
521:Gomory–Hu tree
499:two, with the
495:of arithmetic
480:
477:
460:
455:
452:
449:
444:
441:
424:
421:
348:Main article:
344:A maximum cut.
337:
334:
298:Main article:
294:A minimum cut.
287:
284:
265:weighted graph
106:
103:
62:the cut. In a
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
966:
955:
952:
950:
947:
946:
944:
931:
925:
921:
917:
911:
908:
902:
901:
893:
890:
885:
883:9781584885054
879:
875:
874:
866:
863:
858:
854:
850:
846:
842:
838:
834:
830:
824:
821:
816:
814:3-540-65367-8
810:
806:
802:
796:
793:
787:
782:
778:
774:
773:
768:
764:
758:
755:
740:
736:
729:
725:
719:
716:
710:
706:
700:
697:
692:
690:0-7167-1045-5
686:
682:
678:
677:
672:
668:
662:
659:
654:
652:0-262-03293-7
648:
644:
643:
638:
634:
630:
626:
620:
617:
613:
602:
598:
594:
588:
585:
579:
575:
572:
570:
567:
565:
562:
560:
557:
555:
552:
550:
547:
546:
542:
540:
539:in the tree.
538:
534:
530:
526:
522:
518:
514:
510:
506:
502:
498:
494:
490:
486:
478:
476:
474:
453:
450:
447:
439:
430:
422:
420:
410:
406:
402:
399:
394:
392:
388:
384:
380:
376:
371:
369:
366:(there is an
365:
361:
357:
351:
342:
335:
333:
331:
327:
323:
319:
314:
312:
307:
301:
292:
285:
283:
281:
276:
274:
270:
266:
262:
258:
253:
235:
202:
198:
194:
190:
186:
182:
178:
170:
166:
162:
157:
143:
139:
135:
124:
120:
116:
112:
104:
102:
100:
96:
92:
88:
87:
82:
81:
76:
72:
67:
65:
61:
57:
53:
49:
45:
41:
37:
33:
19:
919:
916:Korte, B. H.
910:
900:Graph Theory
899:
892:
872:
865:
840:
836:
823:
804:
795:
776:
770:
757:
746:, retrieved
734:
718:
708:
699:
674:
661:
640:
619:
611:
605:. Retrieved
596:
587:
536:
532:
528:
524:
493:finite field
489:vector space
484:
482:
428:
426:
423:Sparsest cut
397:
395:
372:
359:
355:
353:
322:network flow
315:
305:
303:
279:
277:
272:
268:
260:
256:
254:
226:
200:
196:
192:
188:
184:
180:
176:
168:
164:
160:
155:
141:
137:
133:
122:
118:
114:
110:
108:
98:
94:
90:
85:
79:
74:
71:flow network
68:
59:
55:
35:
32:graph theory
29:
705:Karp, R. M.
509:cycle space
350:Maximum cut
336:Maximum cut
300:Minimum cut
286:Minimum cut
173:is the set
131:of a graph
943:Categories
748:2019-08-29
607:2021-12-10
580:References
311:bridgeless
225:, then an
105:Definition
857:263871111
485:cut space
479:Cut space
451:
419:problem.
368:odd cycle
364:bipartite
354:A cut is
304:A cut is
158:of a cut
50:into two
40:partition
803:(2004),
739:archived
724:Khot, S.
673:(1979),
639:(2001),
601:Archived
574:Cutwidth
543:See also
413:max-flow
379:APX-hard
95:capacity
83:and the
44:vertices
507:of the
417:min-cut
356:maximum
306:minimum
156:cut-set
99:cut-set
91:cut-set
75:s–t cut
56:cut-set
42:of the
18:Cut set
926:
880:
855:
837:J. ACM
811:
687:
649:
497:modulo
411:. The
389:using
273:weight
267:, the
261:weight
154:. The
80:source
853:S2CID
742:(PDF)
731:(PDF)
513:basis
269:value
213:. If
73:, an
69:In a
60:cross
48:graph
46:of a
38:is a
924:ISBN
878:ISBN
809:ISBN
685:ISBN
647:ISBN
527:and
517:tree
427:The
401:dual
316:The
280:bond
257:size
244:and
217:and
183:) ∈
150:and
86:sink
34:, a
845:doi
781:doi
535:to
448:log
398:not
370:).
271:or
259:or
234:cut
163:= (
136:= (
117:= (
111:cut
36:cut
30:In
945::
851:,
841:56
839:,
777:42
775:,
765:;
733:,
683:,
669:;
635:;
631:;
627:;
610:.
599:.
595:.
475:.
393:.
332:.
313:.
278:A
252:.
203:}
199:∈
195:,
191:∈
187:|
179:,
175:{(
167:,
140:,
121:,
109:A
101:.
933:.
905:.
887:.
860:.
847::
818:.
790:.
783::
752:.
713:.
694:.
656:.
537:t
533:s
529:t
525:s
459:)
454:n
443:(
440:O
360:E
250:T
246:t
242:S
238:s
232:t
230:–
228:s
223:G
219:t
215:s
211:T
207:S
201:T
197:v
193:S
189:u
185:E
181:v
177:u
171:)
169:T
165:S
161:C
152:T
148:S
144:)
142:E
138:V
134:G
129:V
125:)
123:T
119:S
115:C
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
