440:
264:
515:
256:
173:
581:
1139:
435:{\displaystyle \sum _{i=1}^{k-1}\ \sum _{j=i+1}^{k}\sum _{\begin{smallmatrix}v_{1}\in C_{i}\\v_{2}\in C_{j}\end{smallmatrix}}w(\left\{v_{1},v_{2}\right\})}
1101:
Manurangsi, P. (2017). "Inapproximability of
Maximum Edge Biclique, Maximum Balanced Biclique and Minimum k-Cut from the Small Set Expansion Hypothesis".
1012:
982:
944:
689:
670:
1134:
657:-cut where the output partitions have pre-specified sizes. This problem variant is approximable to within a factor of 3 for any fixed
1144:
624:
1129:
623:
max flow computations. Yet, it is easier to analyze the approximation factor of the second algorithm. Moreover, under the
456:
190:
35:
681:
542:
115:
628:
175:
1024:
820:
548:
1058:
1071:
591:
in each of the connected components and removes the lightest one. This algorithm requires a total of
1029:
666:
602:
1050:
883:
750:
66:
38:
problem that requires finding a set of edges whose removal would partition the graph to at least
1042:
978:
940:
923:
901:
856:
1106:
1034:
893:
846:
836:
584:
78:
646:, meaning that the aforementioned approximation algorithms are essentially tight for large
1067:
450:
62:
1075:
1085:
970:
662:
841:
825:"Cutting Up Is Hard To Do: The Parameterised Complexity of k-Cut and Related Problems"
824:
1123:
185:
1054:
1089:
1111:
1103:
44th
International Colloquium on Automata, Languages, and Programming, ICALP 2017
992:
875:
706:
701:
588:
518:
331:
58:
605:
representation of minimum cuts. Constructing the Gomory–Hu tree requires
1013:"A multiagent algorithm for graph partitioning. Lecture Notes in Comput. Sci."
954:
747:
1094:
Proceedings of the fifteenth annual ACM-SIAM symposium on
Discrete Algorithms
1046:
905:
860:
874:
Lokshtanov, Daniel; Saurabh, Saket; Surianarayanan, Vaishali (2022-04-25).
1038:
598:
897:
851:
110:
937:
Computers and
Intractability: A Guide to the Theory of NP-Completeness
601:
computations. Another algorithm achieving the same guarantee uses the
888:
807:
20:
819:
G. Downey, Rodney; Estivill-Castro, Vladimir; Fellows, Michael;
54:
1090:"Approximation schemes for Metric Bisection and partitioning"
612:
max flow computations, but the algorithm requires an overall
533:-cut which separates these vertices among each of the sets.
525:
is part of the input. It is also NP-complete if we specify
928:
Proc. 29th Ann. IEEE Symp. on
Foundations of Comput. Sci.
831:. CATS'03, Computing: the Australasian Theory Symposium.
1066:
Crescenzi, Pierluigi; Kann, Viggo; Halldórsson, Magnús;
963:
Proc. 32nd Ann. IEEE Symp. on
Foundations of Comput. Sci
876:"A Parameterized Approximation Scheme for Min $ k$ -Cut"
661:
if one restricts the graph to a metric space, meaning a
559:
551:
459:
267:
193:
118:
42:
connected components. These edges are referred to as
795:
724:
653:A variant of the problem asks for a minimum weight
631:), the problem is NP-hard to approximate to within
587:that achieves this approximation factor computes a
575:
509:
434:
250:
167:
808:Fernandez de la Vega, Karpinski & Kenyon 2004
53:-cut. This partitioning can have applications in
829:Electronic Notes in Theoretical Computer Science
510:{\displaystyle O{\bigl (}|V|^{k^{2}}{\bigr )}.}
251:{\displaystyle F=\{C_{1},C_{2},\ldots ,C_{k}\}}
760:
499:
465:
19:For the Canadian record producer and DJ, see
8:
736:
245:
200:
159:
125:
673:(PTAS) were discovered for those problems.
95:with an assignment of weights to the edges
1011:Comellas, Francesc; Sapena, Emili (2006),
784:
1110:
1084:Fernandez de la Vega, W.; Karpinski, M.;
1028:
965:, IEEE Computer Society, pp. 743–751
930:, IEEE Computer Society, pp. 444–451
887:
850:
840:
558:
550:
498:
497:
489:
484:
479:
470:
464:
463:
458:
418:
405:
378:
365:
351:
338:
329:
319:
302:
283:
272:
266:
239:
220:
207:
192:
168:{\displaystyle k\in \{2,3,\ldots ,|V|\},}
154:
146:
117:
49:. The goal is to find the minimum-weight
1077:A Compendium of NP Optimization Problems
772:
16:Combinatorial optimization graph problem
717:
1140:Computational problems in graph theory
993:"Approximation algorithms for minimum
991:Guttmann-Beck, N.; Hassin, R. (1999),
935:Garey, M. R.; Johnson, D. S. (1979),
823:; Rosamund, Frances A. (2003-04-01).
671:polynomial time approximation schemes
627:(a conjecture closely related to the
7:
692:can be obtained for this parameter.
690:parameterized approximation scheme
576:{\displaystyle 2-{\tfrac {2}{k}}.}
14:
529:vertices and ask for the minimum
330:
953:Saran, H.; Vazirani, V. (1991),
959:-cuts within twice the optimal"
796:Guttmann-Beck & Hassin 1999
725:Goldschmidt & Hochbaum 1988
545:exist with an approximation of
625:small set expansion hypothesis
480:
471:
429:
393:
155:
147:
1:
842:10.1016/S1571-0661(04)81014-4
1112:10.4230/LIPIcs.ICALP.2017.79
1161:
1135:Combinatorial optimization
639:factor for every constant
36:combinatorial optimization
18:
1074:(2000), "Minimum k-cut",
880:SIAM Journal on Computing
761:Saran & Vazirani 1991
1145:Approximation algorithms
975:Approximation Algorithms
737:Garey & Johnson 1979
543:approximation algorithms
517:However, the problem is
1105:. pp. 79:1–79:14.
629:unique games conjecture
577:
511:
436:
324:
294:
252:
169:
1039:10.1007/s004530010013
578:
512:
437:
298:
268:
253:
170:
65:and communication in
1130:NP-complete problems
977:, Berlin: Springer,
549:
457:
265:
191:
116:
26:In mathematics, the
1096:. pp. 506–515.
798:, pp. 198–207.
667:triangle inequality
665:that satisfies the
1072:Woeginger, Gerhard
1006:, pp. 198–207
971:Vazirani, Vijay V.
898:10.1137/20M1383197
676:While the minimum
573:
568:
507:
432:
389:
387:
386:
248:
165:
67:parallel computing
984:978-3-540-65367-7
946:978-0-7167-1044-8
922:Goldschmidt, O.;
775:, pp. 40–44.
684:parameterized by
669:. More recently,
567:
449:, the problem is
325:
297:
258:while minimizing
73:Formal definition
1152:
1116:
1114:
1097:
1080:
1068:Karpinski, Marek
1062:
1057:, archived from
1032:
1007:
1001:
987:
966:
949:
939:, W.H. Freeman,
931:
910:
909:
891:
871:
865:
864:
854:
844:
816:
810:
805:
799:
793:
787:
782:
776:
770:
764:
758:
752:
745:
739:
734:
728:
722:
687:
680:-cut problem is
679:
660:
656:
649:
645:
638:
622:
611:
597:
585:greedy algorithm
582:
580:
579:
574:
569:
560:
532:
528:
524:
516:
514:
513:
508:
503:
502:
496:
495:
494:
493:
483:
474:
469:
468:
448:
441:
439:
438:
433:
428:
424:
423:
422:
410:
409:
388:
383:
382:
370:
369:
356:
355:
343:
342:
323:
318:
295:
293:
282:
257:
255:
254:
249:
244:
243:
225:
224:
212:
211:
184:
180:
174:
172:
171:
166:
158:
150:
108:
94:
79:undirected graph
52:
46:
41:
31:
1160:
1159:
1155:
1154:
1153:
1151:
1150:
1149:
1120:
1119:
1100:
1083:
1065:
1010:
999:
990:
985:
969:
952:
947:
934:
924:Hochbaum, D. S.
921:
918:
913:
873:
872:
868:
818:
817:
813:
806:
802:
794:
790:
785:Manurangsi 2017
783:
779:
771:
767:
759:
755:
746:
742:
735:
731:
723:
719:
715:
698:
685:
677:
658:
654:
647:
640:
632:
613:
606:
592:
547:
546:
539:
530:
526:
522:
485:
478:
455:
454:
451:polynomial time
446:
414:
401:
400:
396:
385:
384:
374:
361:
358:
357:
347:
334:
263:
262:
235:
216:
203:
189:
188:
182:
178:
114:
113:
96:
81:
75:
63:finite elements
50:
44:
39:
29:
24:
17:
12:
11:
5:
1158:
1156:
1148:
1147:
1142:
1137:
1132:
1122:
1121:
1118:
1117:
1098:
1081:
1063:
1030:10.1.1.55.5697
1023:(2): 279–285,
1008:
988:
983:
967:
950:
945:
932:
917:
914:
912:
911:
882:: FOCS20–205.
866:
811:
800:
788:
777:
765:
753:
749:, which cites
740:
729:
716:
714:
711:
710:
709:
704:
697:
694:
663:complete graph
603:Gomory–Hu tree
572:
566:
563:
557:
554:
538:
537:Approximations
535:
506:
501:
492:
488:
482:
477:
473:
467:
462:
443:
442:
431:
427:
421:
417:
413:
408:
404:
399:
395:
392:
381:
377:
373:
368:
364:
360:
359:
354:
350:
346:
341:
337:
333:
332:
328:
322:
317:
314:
311:
308:
305:
301:
292:
289:
286:
281:
278:
275:
271:
247:
242:
238:
234:
231:
228:
223:
219:
215:
210:
206:
202:
199:
196:
164:
161:
157:
153:
149:
145:
142:
139:
136:
133:
130:
127:
124:
121:
74:
71:
15:
13:
10:
9:
6:
4:
3:
2:
1157:
1146:
1143:
1141:
1138:
1136:
1133:
1131:
1128:
1127:
1125:
1113:
1108:
1104:
1099:
1095:
1091:
1087:
1082:
1079:
1078:
1073:
1069:
1064:
1061:on 2009-12-12
1060:
1056:
1052:
1048:
1044:
1040:
1036:
1031:
1026:
1022:
1018:
1014:
1009:
1005:
998:
996:
989:
986:
980:
976:
972:
968:
964:
960:
958:
951:
948:
942:
938:
933:
929:
925:
920:
919:
915:
907:
903:
899:
895:
890:
885:
881:
877:
870:
867:
862:
858:
853:
848:
843:
838:
834:
830:
826:
822:
821:Prieto, Elena
815:
812:
809:
804:
801:
797:
792:
789:
786:
781:
778:
774:
773:Vazirani 2003
769:
766:
762:
757:
754:
751:
748:
744:
741:
738:
733:
730:
726:
721:
718:
712:
708:
705:
703:
700:
699:
695:
693:
691:
683:
674:
672:
668:
664:
651:
643:
636:
630:
626:
620:
616:
609:
604:
600:
595:
590:
586:
570:
564:
561:
555:
552:
544:
536:
534:
520:
504:
490:
486:
475:
460:
452:
425:
419:
415:
411:
406:
402:
397:
390:
379:
375:
371:
366:
362:
352:
348:
344:
339:
335:
326:
320:
315:
312:
309:
306:
303:
299:
290:
287:
284:
279:
276:
273:
269:
261:
260:
259:
240:
236:
232:
229:
226:
221:
217:
213:
208:
204:
197:
194:
187:
186:disjoint sets
177:
162:
151:
143:
140:
137:
134:
131:
128:
122:
119:
112:
107:
103:
99:
92:
88:
84:
80:
72:
70:
68:
64:
60:
56:
48:
37:
33:
22:
1102:
1093:
1076:
1059:the original
1020:
1017:Algorithmica
1016:
1004:Algorithmica
1003:
994:
974:
962:
956:
936:
927:
879:
869:
832:
828:
814:
803:
791:
780:
768:
756:
743:
732:
720:
675:
652:
641:
634:
618:
614:
607:
593:
540:
453:solvable in
445:For a fixed
444:
105:
101:
97:
90:
86:
82:
76:
43:
27:
25:
852:10230/36518
835:: 209–222.
707:Minimum cut
702:Maximum cut
633:(2 −
589:minimum cut
519:NP-complete
59:data-mining
1124:Categories
1086:Kenyon, C.
916:References
889:2005.00134
1047:0302-9743
1025:CiteSeerX
955:"Finding
906:0097-5397
861:1571-0661
610:− 1
596:− 1
583:A simple
556:−
372:∈
345:∈
327:∑
300:∑
288:−
270:∑
230:…
176:partition
141:…
123:∈
77:Given an
1088:(2004).
1055:25721784
973:(2003),
926:(1988),
696:See also
599:max flow
541:Several
104:→
57:design,
28:minimum
111:integer
109:and an
1053:
1045:
1027:
981:
943:
904:
859:
682:W-hard
644:> 0
642:ε
635:ε
296:
1051:S2CID
1000:(PDF)
997:-cut"
884:arXiv
713:Notes
181:into
34:is a
21:K-Cut
1043:ISSN
1021:3907
979:ISBN
941:ISBN
902:ISSN
857:ISSN
688:, a
55:VLSI
47:-cut
32:-cut
1107:doi
1035:doi
894:doi
847:hdl
837:doi
521:if
85:= (
1126::
1092:.
1070:;
1049:,
1041:,
1033:,
1019:,
1015:,
1002:,
961:,
900:.
892:.
878:.
855:.
845:.
833:78
827:.
650:.
619:kn
100::
89:,
69:.
61:,
1115:.
1109::
1037::
995:k
957:k
908:.
896::
886::
863:.
849::
839::
763:.
727:.
686:k
678:k
659:k
655:k
648:k
637:)
621:)
617:(
615:O
608:n
594:n
571:.
565:k
562:2
553:2
531:k
527:k
523:k
505:.
500:)
491:2
487:k
481:|
476:V
472:|
466:(
461:O
447:k
430:)
426:}
420:2
416:v
412:,
407:1
403:v
398:{
394:(
391:w
380:j
376:C
367:2
363:v
353:i
349:C
340:1
336:v
321:k
316:1
313:+
310:i
307:=
304:j
291:1
285:k
280:1
277:=
274:i
246:}
241:k
237:C
233:,
227:,
222:2
218:C
214:,
209:1
205:C
201:{
198:=
195:F
183:k
179:V
163:,
160:}
156:|
152:V
148:|
144:,
138:,
135:3
132:,
129:2
126:{
120:k
106:N
102:E
98:w
93:)
91:E
87:V
83:G
51:k
45:k
40:k
30:k
23:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.